LeetCode 513

题目链接：找数左下角的值
很容易直接想到层序遍历的方法，这里尝试再用递归实现

class Solution {
    int Deep=-1;
    int result;
    public int findBottomLeftValue(TreeNode root) {
        find(root, 0);
        return result;
    }
    public void find(TreeNode cur, int depth){
        if(cur.left==null&&cur.right==null){
            if(depth>Deep){
                Deep = depth;
                result = cur.val;
            }
        }
        if(cur.left!=null) find(cur.left, depth+1);
        if(cur.right!=null) find(cur.right, depth+1);
    }
}

LeetCode 112

题目链接：路径总和
注意的要点就是递归到底要不要返回值，在只需要找到一条路径的情况下，找到就要立马返回，不用再搜索，所以是肯定需要返回值的

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        
        return pathSum(root, 0, targetSum);
    }
    public boolean pathSum(TreeNode cur, int curSum, int targetSum){
        if(cur==null) return false; //会发生这种情况就是因为这条路径到最后也没有满足情况
        if(cur.left==null&&cur.right==null){
            if(curSum+cur.val==targetSum) return true;
            else return false;
        }
        return pathSum(cur.right, curSum+cur.val, targetSum)||pathSum(cur.left, curSum+cur.val, targetSum);
    }
}

LeetCode 113

题目链接：路径总和2
这里因为是要搜索全部路径，且不用处理递归返回值，所以不需要返回值

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new LinkedList<>();
        if(root==null) return result;
        List<Integer> path = new LinkedList<>();
        findPath(root, 0, targetSum, path, result);
        return result;
    }

    public void findPath(TreeNode cur, int curSum, int targetSum, List<Integer> curPath, List<List<Integer>> result){
        if(cur.left==null&&cur.right==null&&curSum+cur.val==targetSum){
            curPath.add(cur.val);
            result.add(new LinkedList<>(curPath));
            curPath.removeLast();
            return;
        }
        int sum = curSum+cur.val;
        curPath.add(cur.val);
        if(cur.left!=null){
            findPath(cur.left, sum, targetSum, curPath, result);
        } 
        if(cur.right!=null){
            findPath(cur.right, sum, targetSum, curPath, result);
        } 
        curPath.removeLast();
    }
}

LeetCode 106

题目链接：从中序与后序遍历序列构造二叉树
熟悉构造逻辑

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length==0) return null;
        if(inorder.length==1){
            return new TreeNode(inorder[0]);
        }

        int root = postorder[postorder.length-1];
        int index = 0;
        while(index < inorder.length){
            if(inorder[index]==root) break;
            index++;
        }
        TreeNode subRoot = new TreeNode(root,
                                        buildTree(Arrays.copyOfRange(inorder, 0, index), Arrays.copyOfRange(postorder, 0, index)), 
                                        buildTree(Arrays.copyOfRange(inorder, index + 1, inorder.length), Arrays.copyOfRange(postorder, index, inorder.length-1)));
        return subRoot;
    }

}