day018 第六章 二叉树 part05
一、513.找树左下角的值
这个题目的主要思路是使用广度优先搜索（BFS）遍历整棵树，最后返回最后一层的最左边的节点的值。具体的实现可以使用队列来存储每一层的节点，并且在遍历每一层节点时，不断更新最左边的节点的值。时间复杂度为O(n)，其中n是节点的个数。
二、112.路径总和
这个题目的主要思路是使用深度优先搜索（DFS）遍历整棵树，同时记录到达每个节点时的路径和，如果到达叶子节点时路径和等于给定的目标和，则返回true。具体的实现可以使用递归来实现DFS，同时在每个节点处更新路径和，并且在到达叶子节点时判断路径和是否等于目标和。时间复杂度为O(n)，其中n是节点的个数。
三、113.路径总和ii
这个题目的主要思路和112题类似，也是使用DFS遍历整棵树，同时记录到达每个节点时的路径和，并且在到达叶子节点时判断路径和是否等于给定的目标和。不同的是，这个题目需要返回所有满足条件的路径，而不仅仅是返回true或false。具体的实现可以在DFS的过程中使用一个数组来存储当前的路径，并且在到达叶子节点时，如果路径和等于目标和，则将整个路径加入结果列表中。时间复杂度为O(n^2)，其中n是节点的个数，主要是因为每次需要复制一份路径数组。
四、106.从中序与后序遍历序列构造二叉树
这个题目的主要思路是使用递归来构建整棵树。具体的实现可以先找到后序遍历序列中的最后一个节点作为根节点，然后在中序遍历序列中找到根节点的位置，从而确定左子树和右子树的范围。然后递归的构建左子树和右子树即可。时间复杂度为O(n)，其中n是节点的个数。
五、105.从前序与中序遍历序列构造二叉树
这个题目的主要思路和106题类似，也是使用递归来构建整棵树。具体的实现可以先找到前序遍历序列中的第一个节点作为根节点，然后在中序遍历序列中找到根节点的位置，从而确定左子树和右子树的范围。然后递归的构建左子树和右子树即可。时间复杂度为O(n)，其中n是节点的个数。
一、513.找树左下角的值
public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = root.val;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (i == 0) {res = node.val;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return res;
}
二、112.路径总和
public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return sum == root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
三、113.路径总和ii
public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(root, sum, path, res);return res;
}private void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {if (root == null) {return;}path.add(root.val);if (root.left == null && root.right == null && sum == root.val) {res.add(new ArrayList<>(path));}dfs(root.left, sum - root.val, path, res);dfs(root.right, sum - root.val, path, res);path.remove(path.size() - 1);
}
四、106.从中序与后序遍历序列构造二叉树
public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder == null || postorder == null || inorder.length != postorder.length) {return null;}int n = inorder.length;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {map.put(inorder[i], i);}return buildTree(inorder, 0, n - 1, postorder, 0, n - 1, map);
}private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, Map<Integer, Integer> map) {if (inStart > inEnd || postStart > postEnd) {return null;}int rootVal = postorder[postEnd];TreeNode root = new TreeNode(rootVal);int index = map.get(rootVal);int leftSize = index - inStart;root.left = buildTree(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1, map);root.right = buildTree(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1, map);return root;
}
五、105.从前序与中序遍历序列构造二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || preorder.length != inorder.length) {return null;}int n = preorder.length;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {map.put(inorder[i], i);}return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, map);
}private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int index = map.get(rootVal);int leftSize = index - inStart;root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1, map);root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd, map);return root;
}