[LeetCode]513. Find the value in the lower left corner of the tree

513.  Find the value in the lower left corner of the tree 
 Given a binary tree   The root node  root, Please find the of the binary tree   At the bottom   Leftmost   The value of the node .

 Suppose there is at least one node in the binary tree .

 

 Example  1:



 Input : root = [2,1,3]
 Output : 1
 Example  2:



 Input : [1,2,3,4,null,5,6,null,null,7]
 Output : 7
 

 Tips :

 The range of the number of nodes in a binary tree is  [1,104]
-231 <= Node.val <= 231 - 1 

Method 1：BFS

• Sequence traversal , Iterate each layer , Take the leftmost

        public int findBottomLeftValue(TreeNode root) {
    
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            TreeNode res = root;
            while (!q.isEmpty()) {
    
                int size = q.size();
                for (int i = 0; i < size; i++) {
    
                    if (i == 0) res = q.peek();
                    TreeNode cur = q.poll();
                    if (cur.left != null) q.offer(cur.left);
                    if (cur.right != null) q.offer(cur.right);
                }
            }
            return res.val;
        }

Method 2：DFS

• First the left subtree node and then the right subtree node , When the left subtree switches to the right subtree, the maximum depth maxDepth Update and record of , And save the result value

        public int findBottomLeftValue(TreeNode root) {
    
            dfs(root, 0);
            return res;
        }

        int maxDepth = -1, res = 0;

        private void dfs(TreeNode root, int depth) {
    
            if (root == null) return;
            dfs(root.left, depth + 1);
            if (depth > maxDepth) {
    
                maxDepth = depth;
                res = root.val;
            }
            dfs(root.right, depth + 1);
        }

Follow Up: Find the value in the lower right corner of the tree

Method 1：BFS

• Record the last value of each layer

public int findBottomRightValue(TreeNode root) {
    
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    TreeNode res = root;
    while (!q.isEmpty()) {
    
        int size = q.size();
        for (int i = 0; i < size; i++) {
    
            if (i == size - 1) res = q.peek();
            TreeNode cur = q.poll();
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
    }
    return res.val;
}

Method 2：DFS

• Right subtree first and then left subtree

        public int findBottomRightValue(TreeNode root) {
    
            dfs(root, 0);
            return res;
        }

        int maxDepth = -1, res = 0;

        private void dfs(TreeNode root, int depth) {
    
            if (root == null) return;
            dfs(root.right, depth + 1);
            if (depth > maxDepth) {
    
                maxDepth = depth;
                // System.out.printf("%d->",root.val);
                res = root.val;
            }
            dfs(root.left, depth + 1);
        }