class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            root = queue.poll();
            if (root.right != null) {
                queue.offer(root.right);
            }
            if (root.left != null) {
                queue.offer(root.left);
            }
        }
        return root.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 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;

    }
}

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        pathSum(root, targetSum, new ArrayList(), result);
        return result;
    }

    private void pathSum(TreeNode root, int sum, List<Integer> path , List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        if(root.left == null && root.right == null && sum == root.val) {
            result.add(path);
        }
        pathSum(root.left, sum-root.val, new ArrayList(path), result);
        pathSum(root.right, sum-root.val, new ArrayList(path), result);
    }

}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }
        
        int leftSize = rootIndex - inStart;
        int rightSize = inEnd - rootIndex;
        root.left = buildTree(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
        root.right = buildTree(inorder, rootIndex + 1, inEnd, postorder, postEnd - rightSize, postEnd - 1);
        
        return root;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        HashMap<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return solve(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);
    }

    public TreeNode solve(int[]preorder,int preStart,int preEnd,int[]inorder,int inStart,int inEnd,
                        HashMap<Integer,Integer>map){

            if(preStart>preEnd || inStart>inEnd) return null;

            TreeNode root=new TreeNode(preorder[preStart]);

            int inRoot=map.get(root.val);
            int numsLeft=inRoot-inStart;

            root.left=solve(preorder,preStart+1,preStart+numsLeft,inorder,inStart,inRoot-1,map);
            root.right=solve(preorder,preStart+numsLeft+1,preEnd,inorder,inRoot+1,inEnd,map);

            return root;

    }