代码随想录day18|

找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

分析 用层序遍历 最底层的最左节点   递归 记录第一次到达下一层的节点值

class Solution {
    private int Deep=-1;
    private int value=0;

    public int findBottomLeftValue(TreeNode root) {
        if(root==null) return 0;
        dfs(root,0);
        return value;
    }

    private void dfs(TreeNode root,int deep){
        if(root==null) return;
        if(root.left==null&&root.right==null){
            if(deep>Deep){
                value=root.val;
                Deep=deep;
            }
        }
        if(root.left!=null) dfs(root.left,deep+1);
        if(root.right!=null) dfs(root.right,deep+1);
    }
}
//迭代 层序
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque= new LinkedList<>();
        if(root!=null) deque.offer(root);
        int res=0;
        while(!deque.isEmpty()){
            int len=deque.size();
            for(int i=0;i<len;i++){
                TreeNode temp = deque.poll();
                if(i==0){
                    res=temp.val;
                }
                if(temp.left!=null) deque.offer(temp.left);
                if(temp.right!=null) deque.offer(temp.right);
            }
        }

        return res;
    }
}

路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

分析 每次递归 targetSum -= root.val;  判断到叶子节点时 targetSum==0?

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) {
            return false;
        }

        targetSum-=root.val;
        if(root.left==null&&root.right==null){
            return targetSum==0;
        }
        if(root.left!=null){
            boolean left=hasPathSum(root.left,targetSum);
            if(left){
                return true;
            }
        }

        if(root.right!=null){
            boolean right=hasPathSum(root.right,targetSum);
            if(right){
                return true;
            }
        }

        return false;

    }
}

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

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

分析 遍历的逻辑就是分割中序和后序遍历数组，对后序数组来说，数组的最后一个元素一定是根节点，根据根节点的位置，分割中序遍历的数组，分割成leftIn和rightPost，再根据中序分割的位置，分割后序数组，

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){
        if(inBegin>=inEnd||postBegin>=postEnd){
            return null;
        }

        int rootIndex=map.get(postorder[postEnd-1]);//找到根节点
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenIndex=rootIndex-inBegin;
        System.out.println("rootIndex"+rootIndex+" lenIndex"+lenIndex);
        root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+lenIndex);
        root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+lenIndex,postEnd-1);
        return root;
    }
}