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;
}