算法训练营Day18(二叉树)

?找树左下角的值??

本地递归偏难，反而迭代简单属于模板题，?两种方法掌握一下?

我感觉都没什么难的，无非就是记录值而已，

513. 找树左下角的值 - 力扣（LeetCode）? ?

递归法

我来解释一下视频里有人问的 ，只体现深度了，哪里体现最左

注意if(depth>maxDepth)而不是>=，

这里说明，==的时候，也不会记录，这就使得记录的是最左。

class Solution {
    private int maxDepth = Integer.MIN_VALUE;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        travel(root,0);
        return value;
    }
    void travel(TreeNode root,int depth){
        if(root.left==null&&root.right==null){
            if(depth>maxDepth){
                value=root.val;
                maxDepth = depth;
            }
        }
        if(root.left!=null){
            //travel(root.left,depth+1)
            depth++;
            travel(root.left,depth);
            depth--;
        }
        if(root.right!=null){
            depth++;
            travel(root.right,depth);
        }
    }
}

迭代法

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if(root!=null){
            deque.add(root);
        }
        int res = 0;
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if(i==0){
                    res = poll.val;
                }
                if(poll.left!=null){
                    deque.add(poll.left);
                }
                if(poll.right!=null){
                    deque.add(poll.right);
                }
            }
        }
        return res;
    }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if(root!=null){
            deque.add(root);
        }
        //存放最后一层
        Deque<TreeNode> res = new LinkedList<>() ;
        while (!deque.isEmpty()){
            //每次更新
            res = new LinkedList<>();
            int size = deque.size();
            while (size-->0){
                TreeNode poll = deque.poll();
                res.add(poll);
                if(poll.left!=null){
                    deque.add(poll.left);
                }
                if(poll.right!=null){
                    deque.add(poll.right);
                }
            }
        }
        return res.poll().val;
    }
}

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 flag =hasPathSum(root.left,targetSum);
            if(flag) return true;
        }
        if(root.right!=null){
            boolean flag = hasPathSum(root.right,targetSum);
            if(flag) return true;
        }
        return false;
    }
}

class Solution {
   private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root==null){return res;}
        hashPathSum(root,targetSum,new ArrayList<>());
        return res;
    }
    private void hashPathSum(TreeNode root,int targetSum,List<Integer> path){
        
        targetSum-=root.val;
        path.add(root.val);
        if(root.left==null&&root.right==null){
            if(targetSum==0){
                res.add(new ArrayList<>(path));
            }
        }
        if(root.left!=null){
            hashPathSum(root.left,targetSum,path);
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            hashPathSum(root.right,targetSum,path);
            path.remove(path.size()-1);
        }

    }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // [9,3,15,20,7] 左根右
        // [9,15,7,20,3] 左右根
        if(inorder==null || postorder == null || inorder.length != postorder.length){
            return null;
        }
        //空间换时间去找结点。
        HashMap<Integer,Integer> valueIndexMap = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            valueIndexMap.put(inorder[i],i);
        }
        return f(inorder,0,inorder.length-1,postorder,0,postorder.length-1,valueIndexMap);
    }
    public static TreeNode f(int []in ,int L1,int R1,int [] post,int L2,int R2 
        ,HashMap<Integer,Integer> valueIndexMap){
        //健壮性考虑
        if(L1>R1 || L2>L2)return null;
        TreeNode head = new TreeNode(post[R2]);
        //找头结点，
        int find = valueIndexMap.get(post[R2]);
        //递归
        head.left = f(in,L1,find-1,post,L2,L2+find-L1-1,valueIndexMap);
        head.right= f(in,find+1,R1,post,L2+find-L1,R2-1,valueIndexMap);
        return head;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //[3,9,20,15,7]根左右
        //[9,3,15,20,7]左根右
        if(preorder == null || inorder == null || preorder.length !=  inorder.length){
            return null;
        }
        HashMap<Integer,Integer> valueIndexMap = new HashMap<>();
        for(int i = 0; i<inorder.length;i++){
            valueIndexMap.put(inorder[i],i);
        }
        return f(preorder,0,preorder.length-1,inorder,0,inorder.length-1,valueIndexMap);
        
    }
    public static TreeNode f(int [] pre,int L1,int R1,int[] in,int L2,int R2,
            HashMap<Integer,Integer> valueIndexMap){
            if(L1 > R1||L2>R2){
                return null;
            }
            TreeNode head = new TreeNode(pre[L1]);
            //去中序里找头
            int find = valueIndexMap.get(pre[L1]);
            //递归
            head.left = f(pre,L1+1,L1+1+find-L2+1,in,L2,find-1,valueIndexMap);
            head.right = f(pre,L1+find-L2+1,R1,in,find+1,R2,valueIndexMap);
            return head;
        }
}