树的更层知识，算是把之前学的理论都实践了，有点难度想了挺久的。

1.力扣513（找树左下角的值）

        本题依旧利用递归三部曲来解决，我们要先确定遍历顺序，我们需要找的节点是左下角的值，所以我们应该利用的遍历顺序是把左放在前面的遍历顺序就可以，所以前中后序遍历都可以；接下来我们要取得节点应满足深度最大，并且在深度相同的情况下取最边的值。

1.递归法

接下来我们利用递归三部曲来解决问题：

• 确定递归函数的参数和返回值：参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void（本题还需要类里的两个全局变量，用maxDepth来记录最大深度，res记录最大深度最左节点的数值。）

    int maxDepth = Integer.MIN_VALUE;
    int res = 0;
    public void findValue(TreeNode root,int depth) 

• 确定终止条件：当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度，在更新深度的同时进行判断，若深度最大我们就要更新数值。

        if(root.left==null&&root.right==null){
            if(depth>maxDepth){//若深度最大就更新结果
                maxDepth=depth;
                res=root.val;
            }
        }

• 确定单层递归的逻辑：在找最大深度的时候，递归的过程中依然要使用回溯，因为每个节点的深度是变化的。(可以理解下回溯的过程，第二种写法更好理解)

        if(root.left!=null){
            //回溯的过程
            findValue(root.left,depth+1);
            //第二种写法
//            depth++;
//            findValue(root.left,depth);
//            depth--;
        }
        if(root.right!=null){
            //回溯的过程
            findValue(root.right,depth+1);
            //第二种写法
//            depth++;
//            findValue(root.right,depth);
//            depth--;
        }

2.迭代法

        本题的迭代法也就是二叉树的层序遍历，只是我们在遍历至最后一层时，我们把最后一层的首元素进行弹出操作，代码好写，思路的话只要理解了层序遍历就会很快的写出来。（有代码注释）

下面是代码：

    public int findBottomLeftValue(TreeNode root) {
        //创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return 0;
        }
        //存入根节点
        queue.offer(root);
        //存结果
        List<List<Integer>> res = new ArrayList<>();
        while(!queue.isEmpty()){、
            //每一层的list集合
            List<Integer> temp = new ArrayList();
            int size = queue.size();
            //遍历出每一层的元素
            while(size>0){
                //弹出元素
                TreeNode node = queue.poll();
                temp.add(node.val);
                //存入弹出节点的左孩子
                if(node.left!=null){
                    queue.offer(node.left);
                }
                //存入弹出节点的右孩子
                if(node.right!=null){
                    queue.offer(node.right);
                }
                size--;
            }
            res.add(temp);
        }
        //取出结果集中的尾集合的首元素
        return res.get(res.size()-1).get(0);
    }

2.力扣112（路经总和）

        本题学到了很重要的知识，就是什么时候进行返回结果，什么时候不需要返回：

• 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
• 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
• 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

        本题继续利用递归遍历整个二叉树，若我们遍历到叶子节点的时候，我们就需要判断这个路径的和是否是满足我们的目标和。接下来我们利用递归三部曲来解决：

• 确定递归函数的参数和返回类型参：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。

    public boolean findSum(TreeNode root, int count)

• 确定终止条件：我们可以利用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。如果遍历到了叶子节点，count不为0，就是没找到。

        if(root.left==null&&root.right==null&&count==0){//满足条件
            return true;
        }
        if(root.left==null&&root.right==null){//不满足返回false
            return false;
        }

• 确定单层递归的逻辑：因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了，递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。

        //遍历左子树
        if(root.left!=null){
            //若左子树满足就直接返回
            if(findSum(root.left,count-root.left.val)){
                return true;
            }
        }
        //遍历右子树
        if(root.right!=null){
            //若右子树满足就直接返回
            if(findSum(root.right,count-root.right.val)){
                return true;
            }
        }
        //若不满足就返回false
        return false;

整体代码：

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        return findSum(root,targetSum-root.val);
    }
    public boolean findSum(TreeNode root, int count) {
        if(root.left==null&&root.right==null&&count==0){
            return true;
        }
        if(root.left==null&&root.right==null){
            return false;
        }
        //遍历左子树
        if(root.left!=null){
            //若左子树满足就直接返回
            if(findSum(root.left,count-root.left.val)){
                return true;
            }
        }
        //遍历右子树
        if(root.right!=null){
            //若右子树满足就直接返回
            if(findSum(root.right,count-root.right.val)){
                return true;
            }
        }
        //若不满足就返回false
        return false;
    }

3.力扣106（从中序与后序遍历序列构建二叉树）

        本题也是利用递归，首先我们要知道通过遍历序列来构建二叉树只能有两种：前序和中序，中序和后序。明白了这点后我们来解决本题，构建二叉树的思路就是，我们通过前序或者后序来找出中节点，然后通过中节点来切割中序数组，然后再来切割后续数组，接着我们再把切割的数组进行递归创建。我这里把卡哥的图片放上，很好理解

 我们再切割好前序数组和后序数组后，把前序数组的左和后续数组的左进行递归构建左子树，同理来构建右子树。

有卡哥总结的几步构建二叉树的步骤：

• 第一步：如果后序数组大小为零的话，说明是空节点了。

• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

• 第五步：切割后序数组，切成后序左数组和后序右数组

• 第六步：递归处理左区间和右区间

 下面是实现代码（标注了步骤）：

    public TreeNode buildTree(int[] inorder,int[] postorder) {
        if(inorder.length==0||postorder.length==0){
            return null;
        }
        return travleTree(inorder,postorder);
    }

    public TreeNode travleTree(int[] inorder,int[] postorder) {
        // 1.如果后序数组大小为零的话，说明是空节点了。
        if(postorder.length==0){
            return null;
        }
        //2.那么取后序数组最后一个元素作为节点元素。
        int rootValue = postorder[postorder.length-1]; 
        TreeNode root = new TreeNode(rootValue);
        //3.后序数组最后一个元素在中序数组的位置，作为切割点
        int index = 0;
        for(;index<inorder.length;index++){
            if(inorder[index]==rootValue){
                break;
            }
        }
        //4.切割中序数组，切成中序左数组和中序右数组
        int[] leftInoreder = Arrays.copyOfRange(inorder,0,index);
        int[] rightInoreder = Arrays.copyOfRange(inorder,index+1,inorder.length);
        //5.切割后序数组，切成后序左数组和后序右数组
        int[] leftPostorder = Arrays.copyOfRange(postorder,0,index);
        int[] rightPostorder = Arrays.copyOfRange(postorder,index,postorder.length-1);      
        //6.递归处理左区间和右区间
        root.left = buildTree(leftInoreder,leftPostorder);
        root.right = buildTree(rightInoreder,rightPostorder);
        return root;
    }