day18 二叉树 part05

513. 找树左下角的值

中等
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
层序遍历可以直接秒了，但是这里我们用递归的办法
请注意这里：回溯隐藏在这里！

class Solution {
    private int Deep = 0; // 用于记录最大深度
    private int val = 0;  // 题目假设至少有一个节点，不用担心根节点为空，导致val结果就是初始化结果

    public int findBottomLeftValue(TreeNode root) {
        findLeftValue(root, 1);

        return val;
    }
    public void findLeftValue(TreeNode node, int deep) {
        if (node == null) {
            return; // 如果节点为空自然是对val和Deep不做任何处理
        }
        if (Deep < deep) { // 如果此时最大深度小于当前深度，如果最大深度大于等于当前深度了，那就说明以前已经有一样深或更深的左节点（因为我们是先递归左节点，再递归右节点，怎么也不可能先找着右节点，除非深度更深）被访问过了，就不用记录当前节点了
            Deep++; // 更新深度
            val = node.val; //说明val值还不是最底层的值，需要更新一下
        }
        findLeftValue(node.left, deep + 1); // 隐藏着回溯
        findLeftValue(node.right, deep + 1); // 隐藏着回溯
        
    }
}

112. 路径总和

简单
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
这题我一下就做出来了……虽然我有的地方还没有特别想通，但我感觉都是一个套路，一写就秒了

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return traversal(root, targetSum);
    }
    public boolean traversal(TreeNode node, int targetSum){
        if (node == null) {
            return false;
        }
        if (node.left == null && node.right == null){ // 如果当前节点是叶子节点，就判断它满不满足目标和
            if (node.val == targetSum){
                return true;
            }
        }
        boolean leftBool = traversal(node.left, targetSum - node.val);  //隐藏着回溯
        boolean rightBool = traversal(node.right, targetSum - node.val); //隐藏着回溯

        return leftBool || rightBool; //这里不是&&，因为是在左右两条路里找到一条合格的就行
    }
}

113. 路径总和 II

中等
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>(); //存放最终结果
        List<Integer> path = new ArrayList<>(); // 存放单独一条路径

        traversal(root, targetSum, res, path);

        return res;
    }
    public void traversal(TreeNode node, int targetSum, List<List<Integer>> res, List<Integer> path) {
        if (node == null) {
            return; // 如果这个节点是空的，那肯定不能把它添加进路径
        }

        if (node.left == null && node.right == null) { // 是否为叶子节点
            if(node.val == targetSum){
                path.add(node.val);
                res.add(new ArrayList<>(path)); // res.add(path);不能这么写！！！
                path.remove(path.size() - 1);
            }
            return; // 叶子节点下面肯定是空，没有必要继续遍历后面了
        }
        path.add(node.val);
        traversal(node.left, targetSum - node.val, res, path);
        path.remove(path.size() - 1);
        
        path.add(node.val);
        traversal(node.right, targetSum - node.val, res, path);
        path.remove(path.size() - 1);
    }
}

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

中等
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

难点：根节点的左右子树在无论前序，中序，后序都是会以某个元素为界限分开的，而不会说，交叉着来，归根到底是因为，无论中左右，左中右，左右中，都是左在先，右在后，在没有把左子树遍历完之前，是不会访问右子树的

难点：这个题不是让你真的输出这种 [3,9,20,null,null,15,7]，而是你返回一个root节点，root是二叉树的根节点就行。

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++){
            valToIndex.put(inorder[i], i); // 这里是建立中序的索引，不是后序的，因为中序可以将遍历数组分成两半
        }
        // inorder.length - 1 代表的是最后一个元素的索引，所以要 - 1
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    /* 
    build 函数的定义：
    后序遍历数组为 postorder[postStart..postEnd]，
    中序遍历数组为 inorder[inStart..inEnd]，
    构造二叉树，返回该二叉树的根节点 
*/
    public TreeNode build(int[] inorder, int inStart, int inEnd, 
                        int[] postorder, int postStart, int postEnd){
        if (inStart > inEnd) return null; // 最多就是inStart 等于InEnd（当中序遍历数组只有一个元素时）
        int rootVal = postorder[postEnd]; // root节点对应的值就是后序遍历数组的最后一个元素
        int rootIndex = valToIndex.get(rootVal); // rootVal 在中序遍历数组中的索引
        TreeNode root = new TreeNode(rootVal);
        int leftSize = rootIndex - inStart;

        root.left = build(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
        root.right = build(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);

        return root;
    }
}

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

中等
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

class Solution {
    HashMap<Integer, Integer> valToIndex = new HashMap<>(); // 存放中序（别忘了写new）

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++){
            valToIndex.put(inorder[i], i);
        }

        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    public TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;

        int rootVal = preorder[preStart];
        int rootIndex = valToIndex.get(rootVal);
        int leftSize = rootIndex - inStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);

        return root;
    }
}