二叉树part05 算法

二叉树part05 算法

****今日内容

●??513.找树左下角的值

●??112.?路径总和??113.路径总和ii

●??106.从中序与后序遍历序列构造二叉树?105.从前序与中序遍历序列构造二叉树

1.513.找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //定义在全局 属性
    int maxDepth=Integer.MIN_VALUE;
    int result;
    public int findBottomLeftValue(TreeNode root) {
        //能判断左叶子节点了，那怎么判断最底层的左叶子节点
        //那就每次都记录以下当前深度，直到遇到叶子节点，将这个叶子节点深度和定义在全局的叶子节点深度进行比较，如果叶子节点深度大就更新全局的深度变量，然后记录当前左下角的值
        //int curDepth;
        findCurDepth(root,0);
        return result;
    }
    public void findCurDepth(TreeNode root,int curDepth){
        //终止条件
        if(root.left==null&&root.right==null){
            //比较当前的深度
            if(curDepth>maxDepth){
                //更新最大深度值
                maxDepth=curDepth;
                //更新左下角的值
                result=root.val;
            }
        }
        if(root.left!=null){
            //每次遍历一个节点，深度+1
            curDepth++;
            findCurDepth(root.left,curDepth);
            //函数调用完毕后，全局属性值已经被更新
            //这里的深度变量已经用完，我们要让他恢复（回溯）
            curDepth--;
        }
        if(root.right!=null){
            curDepth++;
            findCurDepth(root.right,curDepth);
            curDepth--;
        }
    }
    
}

2.112.?路径总和

https://leetcode.cn/problems/path-sum/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        return curPathSum(root,targetSum-root.val);
    }
    public boolean curPathSum(TreeNode root,int curSum){
        //将现在的cueSum初始化未目标值，后面每遍历一个节点，就让他减下去，如果最终减为0，那么证明这个路径存在

        //写终止条件
        //当为叶子节点并且curSum减为0
        if(root.left==null&&root.right==null&&curSum==0){
            return true;
        }
        //当为叶子节点但是curSum不为0
        if(root.left==null&&root.right==null&&curSum!=0){
            return false;
        }
        //每层的遍历
        if(root.left!=null){
            //将curSum做减掉操作
            curSum-=root.left.val;
            boolean left=curPathSum(root.left,curSum);
            //如果已经找到了路径和为目标值，那么就返回true
            if(left){
                return true;
            }
            //如果找不到路径和为目标值，那么就接着下去遍历新的路径，那么在进行新的前需要将curSum回溯到原来的值
            //将curSum回溯到原来的值
            curSum+=root.left.val;
        }

        if(root.right!=null){
            curSum-=root.right.val;
            boolean right=curPathSum(root.right,curSum);
            if(right){
                return true;
            }
            curSum+=root.right.val;
        }
        //以上都不是，那么就返回false
        return false;
    }
}

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

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //哈希表，保存元素，下标
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
        //1.后续数组为0，空节点
        //如果后序数组为空，那么就证明没有根节点，也就不存在二叉树，返回null
        if(inBegin>=inEnd||postBegin>=postEnd){
            //不满足左闭右开，说明没有元素
            return null;
        }
        //2.后序数组最后一个元素为节点元素
        //如果不为空，那就定义一个下标保存着最后一个元素下标
        //后序数组最后一个元素下标作为根节点
        int rootIndex=map.get(postorder[postEnd-1]);
        //定义一颗根节点为rootIndex的二叉树
        TreeNode root=new TreeNode(inorder[rootIndex]);

        //3.寻找中序数组位置作为切割点
        //保存中序左子树个数，用来确定后序数列的个数
        int lenOfLeft=rootIndex-inBegin;

        root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+lenOfLeft);//左中序，左后序
        root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+lenOfLeft,postEnd-1);//右中序，右后序
        return root;

    }
}