2020-3-17

1160.拼写单词

✒解题思路：

1. 将字符表chars的字母个数用数组保存起来，遍历每个词汇word，将word的字母个数也用数组保存比较其字母的个数即可。

class Solution {
	public int countCharacters(String[] words, String chars) {
		int[] countChars = counter(chars);
		int result = 0;
		for (String s : words) {
			boolean flag = true;
			int[] countWord = counter(s);
			for (int i = 0; i < 26; i++) {
				if (countChars[i] < countWord[i]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				result += s.length();
			}
		}
		return result;
	}

	private int[] counter(String chars) {
		int[] result = new int[26];
		for (int i = 0; i < chars.length(); i++) {
			char ch = chars.charAt(i);
			result[ch - 'a'] += 1;
		}
		return result;
	}
}

105.从前序和中序遍历序列构造二叉树

✒解题思路：

1. 先从前序序列中获取根节点，然后在中序序列中找到根节点的位置，并将中序序列划分为左右子树，然后递归创建左右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		int len = preorder.length;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < len; i++) {
			map.put(inorder[i], i);
		}
		return helper(preorder, 0, len - 1, inorder, 0, len - 1, map);
	}

	private TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap<Integer, Integer> map) {
		if (preStart > preEnd) {
			return null;
		}
		int rootValue = preorder[preStart];
		int rootIndex = map.get(rootValue);
		int len = rootIndex - inStart;
		TreeNode root = new TreeNode(rootValue);
		root.left = helper(preorder, preStart + 1, 
				preStart + len, inorder, inStart, rootIndex - 1, map);
		root.right = helper(preorder, preStart + len + 1, 
				preEnd, inorder, rootIndex + 1, inEnd, map);
		return root;
	}
}

106.从后序和中序遍历序列构造二叉树

✒解题思路：

1. 先从后序序列中获取根节点，然后在中序序列中找到根节点的位置，并将中序序列划分为左右子树，然后递归创建左右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		int len = inorder.length;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < len; i++) {
			map.put(inorder[i], i);
		}
		return helper(inorder, 0, len - 1, postorder, 0, len - 1, map);
	}

	private TreeNode helper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, HashMap<Integer, Integer> map) {
		if (postStart > postEnd) {
			return null;
		}
		int rootValue = postorder[postEnd];
		int rootIndex = map.get(rootValue);
		int len = rootIndex - inStart;
		TreeNode root = new TreeNode(rootValue);
		root.left = helper(inorder, inStart, rootIndex - 1,
				postorder, postStart, postStart + len - 1, map);
		root.right = helper(inorder, rootIndex + 1, inEnd,
				postorder, postStart + len, postEnd - 1, map);
		return root;
	}
}

109.有序链表转换二叉搜索树

✒解题思路：

1. 使用快慢指针，当快指针走向链表尾部，慢指针指向中间节点的前一个节点，使用中间节点作为根节点，然后分别创建左右子树。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public TreeNode sortedListToBST(ListNode head) {
		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return new TreeNode(head.val);
		}
		ListNode pre = head;
		ListNode fast = head.next.next;
		while (fast != null && fast.next != null) {
			pre = pre.next;
			fast = fast.next.next;
		}
		int rootValue = pre.next.val;
		TreeNode root = new TreeNode(rootValue);
		ListNode rightHead = pre.next.next;
		pre.next = null;
		root.left = sortedListToBST(head);
		root.right = sortedListToBST(rightHead);
		return root;
	}
}

113.路径总和II

✒解题思路：

1. 从根节点开始遍历，直到遇见叶子节点并且路径和为sum，将该条路径加入结果，之后删点该叶子节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> lists = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		getLists(root, path, lists, sum);
		return lists;
	}

	private void getLists(TreeNode root, List<Integer> path, List<List<Integer>> lists, int sum) {
		if (root == null) {
			return;
		}
		path.add(root.val);
		sum -= root.val;
		if (root.left == null && root.right == null && sum == 0) {
			lists.add(new ArrayList<>(path));
		}
		if (root.left != null) {
			getLists(root.left, path, lists, sum);
		}
		if (root.right != null) {
			getLists(root.right, path, lists, sum);
		}
		path.remove(path.size() - 1);
	}
}

114.二叉树展开为链表

✒解题思路：

1. 从根节点开始遍历，若无左节点，则root = root.right；若有左节点，将右子树放在左子树的最右节点后，然后将左子树放在根节点的右子树上，根节点的左子树为空。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public void flatten(TreeNode root) {
		while (root != null) {
			if (root.left == null) {
				root = root.right;
			} else {
				TreeNode temp = root.left;
				while (temp.right != null) {
					temp = temp.right;
				}
				temp.right = root.right;
				root.right = root.left;
                root.left = null;
				root = root.right;
			}
		}
	}
}

1302.层次最深叶子节点的和

✒解题思路：

1. 层次遍历树，记录每层的节点之和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public int deepestLeavesSum(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		int result = 0;
		queue.offer(root);
		while (!queue.isEmpty()) {
			result = 0;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode temp = queue.poll();
				result += temp.val;
				if (temp.left != null) {
					queue.offer(temp.left);
				}
				if (temp.right != null) {
					queue.offer(temp.right);
				}
			}
		}
		return result;
	}
}

1315.祖父节点值为偶数的节点和

✒解题思路：

1. 层次遍历树，遇见节点值为偶数，加上将其孙子节点的和。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public int sumEvenGrandparent(TreeNode root) {
		return dfs(root);
	}

	private int dfs(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if ((root.val & 1) == 0) {
			return getChildSum(root.left) + getChildSum(root.right) + dfs(root.left) + dfs(root.right);
		} else {
			return dfs(root.left) + dfs(root.right);
		}
	}

	private int getChildSum(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int leftNum = root.left == null ? 0 : root.left.val;
		int rightNum = root.right == null ? 0 : root.right.val;
		return leftNum + rightNum;
	}
}

513.找树左下角的值

✒解题思路：

1. 层次遍历树，返回最后一层的第一个节点值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		int result = 0;
		queue.offer(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode temp = queue.poll();
                if(i == 0){
                    result = temp.val;
                }
				if (temp.left != null) {
					queue.offer(temp.left);
				}
				if (temp.right != null) {
					queue.offer(temp.right);
				}
			}
		}
		return result;
    }
}