[high frequency written test questions] 513 Find the value in the lower left corner of the tree

Title Description

This is a LeetCode Upper 513. Find the value in the lower left corner of the tree , The difficulty is secondary .

Tag : 「BFS」、「DFS」、「 Tree traversal 」

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

BFS

Use BFS Conduct 「 Sequence traversal 」, Update each time with the first node of the current layer ans, When BFS After the end ,ans The storage is the leftmost node of the last layer .

Code ：

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        int ans = 0;
        while (!d.isEmpty()) {
            int sz = d.size();
            ans = d.peek().val;
            while (sz-- > 0) {
                TreeNode poll = d.pollFirst();
                if (poll.left != null) d.addLast(poll.left);
                if (poll.right != null) d.addLast(poll.right);
            }
        }
        return ans;
    }
}

• Time complexity ：
• Spatial complexity ： In the worst case, all nodes are on the same layer , The complexity is

DFS

Empathy , have access to DFS Traverse the tree , Priority each time DFS The left subtree of the current node , Search to the current depth for the first time depth when , It must be the leftmost node of the current depth , In this case, the current node value is used to update ans.

Code ：

class Solution {
    int max, ans;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return ans;
    }
    void dfs(TreeNode root, int depth) {
        if (root == null) return ;
        if (depth > max) {
            max = depth; ans = root.val;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

• Time complexity ：
• Spatial complexity ： Degenerate into chain in the worst case , The recursion depth is . The complexity is

Last

This is us. 「 Brush through LeetCode」 The first of the series No.513 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .