LeetCode刷题Day15——二叉树（树左下角的值、路径和、树的构造、最大二叉树、合并二叉树）

/**
 * <pre>
 * 1.广搜，每一层遍历，找到最左边的节点记录下值
 * 2.深搜，找到最深的一层就将结果记录下来，先遍历的是左节点，所以右节点如果同样高度则不会覆盖掉左节点的值，保证了最终找到的是最左边的节点
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/16 13:44
 */
public class 找树左下角的值513 {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = root.val;
        boolean flag = true; // 此处也可以不使用flag，而是每次offer入队的时候先入right节点，那么最后一次poll出来的节点就是当层最左边的节点
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i=0; i<size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                    if (flag) {
                        ans = poll.left.val;
                        flag = false;
                    }
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                    if (flag) {
                        ans = poll.right.val;
                        flag = false;
                    }
                }
            }
            flag = true;
        }
        return ans;
    }
    int res = 0;
    int maxHeight = -1;
    public int findBottomLeftValue2(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    public void dfs(TreeNode root, int height) {
        if (root.left == null && root.right == null) {
            if (height > maxHeight) {
                maxHeight = height;
                res = root.val;
            }
            return;
        }
        if (root.left != null) {
            dfs(root.left, height+1);
        }
        if (root.right != null) {
            dfs(root.right, height+1);
        }
    }
}

/**
 * <pre>
 * 1.深搜
 * 2.广搜
 * 节点的值有可能是负数，所以不能大于targetSum就剪枝
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/16 15:19
 */
public class 路径总和112 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return dfs(root, targetSum, root.val);
    }
    public boolean dfs(TreeNode root, int targetSum, int nowSum) {
        if (root.left == null && root.right == null) {
            return nowSum == targetSum;
        }
        boolean rs1=false, rs2=false;
        if (root.left != null) {
            rs1 = dfs(root.left, targetSum, nowSum+root.left.val);
        }
        if (root.right != null) {
            rs2 = dfs(root.right, targetSum, nowSum+root.right.val);
        }
        return rs1 || rs2;
    }
    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();
        nodeQueue.offer(root);
        sumQueue.offer(root.val);
        while (!nodeQueue.isEmpty()) {
            int size = nodeQueue.size();
            for (int i=0; i<size; i++) {
                TreeNode node = nodeQueue.poll();
                Integer sum = sumQueue.poll();
                if (node.left == null && node.right == null) {
                    if (sum == targetSum) {
                        return true;
                    }
                }
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    sumQueue.offer(sum+node.left.val);
                }
                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    sumQueue.offer(sum+node.right.val);
                }
            }
        }
        return false;
    }
}

/**
 * <pre>
 * 递归：从前往后依次取出前缀遍历数组的值，以其作为分割点，不断将中序数组分割为左右子树
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/16 17:24
 */
public class 从前序与中序遍历序列构造二叉树105 {
    int pre_idx = 0;
    int[] preorder;
    int[] inorder;
    Map<Integer, Integer> idx_map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int index = 0;
        for (int val : inorder) {
            idx_map.put(val, index++);
        }
        return build(0, inorder.length-1);
    }
    public TreeNode build(int in_left, int in_right) {
        if (in_left > in_right) {
            return null;
        }
        int val = preorder[pre_idx++];
        TreeNode root = new TreeNode(val);
        Integer index = idx_map.get(val);
        root.left = build(in_left, index-1);
        root.right = build(index+1, in_right);
        return root;
    }
}

/**
 * <pre>
 * 递归：从后往前依次取出前缀遍历数组的值，以其作为分割点，不断将中序数组分割为右左子树
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/16 16:21
 */
public class 从中序与后序遍历序列构造二叉树106 {
    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer, Integer> idx_map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        post_idx = postorder.length - 1;
        int index = 0;
        for (int val : inorder) {
            idx_map.put(val, index++);
        }
        return build(0, inorder.length-1);
    }
    public TreeNode build(int in_left, int in_right) {
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return null;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map.get(root_val);
        // 下标减一
        post_idx--;
        // 先构造右子树，因为从后取后序遍历数组的值，去完根节点后接着最开始取到的就是最右边的节点
        root.right = build(index + 1, in_right);
        // 构造左子树
        root.left = build(in_left, index - 1);
        return root;
    }
}

/**
 * <pre>
 * 递归
 * 单调栈
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 11:45
 */
public class 最大二叉树654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode();
        int max = nums[0], index=0;
        for (int i=1; i<nums.length; i++) {
            if (nums[i] > max) {
                index = i;
                max = nums[i];
            }
        }
        root.val = max;
        root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, index));
        root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, index+1, nums.length));
        return root;
    }
}

/**
 * <pre>
 * 1.深搜
 * 2.广搜
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 12:23
 */
public class 合并二叉树617 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = mergeTrees(root1.left, root2.left);
        merged.right = mergeTrees(root1.right, root2.right);
        return merged;
    }
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        Queue<TreeNode> treeQueue1 = new LinkedList<>();
        Queue<TreeNode> treeQueue2 = new LinkedList<>();
        Queue<TreeNode> mergedQueue = new LinkedList<>();
        treeQueue1.offer(root1);
        treeQueue2.offer(root2);
        TreeNode ans = new TreeNode(root1.val + root2.val);
        mergedQueue.offer(ans);
        while (!treeQueue1.isEmpty() || !treeQueue2.isEmpty()) {
            TreeNode treeNode1 = treeQueue1.poll();
            TreeNode treeNode2 = treeQueue2.poll();
            TreeNode root = mergedQueue.poll();
            TreeNode mergedNode1, mergedNode2;
            if (treeNode1.left == null) {
                mergedNode1 = treeNode2.left;
            } else if (treeNode2.left == null) {
                mergedNode1 = treeNode1.left;
            } else {
                treeQueue1.offer(treeNode1.left);
                treeQueue2.offer(treeNode2.left);
                mergedNode1 = new TreeNode(treeNode1.left.val + treeNode2.left.val);
                mergedQueue.offer(mergedNode1);
            }
            root.left = mergedNode1;
            if (treeNode1.right == null) {
                mergedNode2 = treeNode2.right;
            } else if (treeNode2.right == null) {
                mergedNode2 = treeNode1.right;
            } else {
                treeQueue1.offer(treeNode1.right);
                treeQueue2.offer(treeNode2.right);
                mergedNode2 = new TreeNode(treeNode1.right.val + treeNode2.right.val);
                mergedQueue.offer(mergedNode2);
            }
            root.right = mergedNode2;
        }
        return ans;
    }
}