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

source ： Power button （LeetCode）

describe ：

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,10⁴]
• -2³¹ <= Node.val <= 2³¹ - 1

Method 1 ： Depth-first search
Use height Record the height of the node traversed , curVal Record height at curHeight The value of the leftmost node of . In depth first search , First, we search the left child node of the current node , Then search the right child node of the current node , Then judge the height of the current node height Is it greater than curHeight, If it is , It will be curVal Set to the value of the current node , curHeight Set to height.

Because we first traverse the left subtree , And then traverse the right subtree , So for all nodes at the same height , The leftmost node must be the first to be traversed .

Code ：

class Solution {
    
public:
    void dfs(TreeNode *root, int height, int &curVal, int &curHeight) {
    
        if (root == nullptr) {
    
            return;
        }
        height++;
        dfs(root->left, height, curVal, curHeight);
        dfs(root->right, height, curVal, curHeight);
        if (height > curHeight) {
    
            curHeight = height;
            curVal = root->val;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
    
        int curVal, curHeight = 0;
        dfs(root, 0, curVal, curHeight);
        return curVal;
    }
};

Execution time ：4 ms, In all C++ Defeated in submission 97.07% Users of
Memory consumption ：21 MB, In all C++ Defeated in submission 97.09% Users of
Complexity analysis
Time complexity ： O(n), among n Is the number of nodes in the binary tree . Need to traverse n Nodes .
Spatial complexity ： O(n). Recursive stack needs to occupy O(n) Space .

Method 2 ： Breadth first search

Use breadth first search to traverse the nodes of each layer . When traversing a node , You need to put its non empty right child node into the queue first , Then put its non empty left child nodes into the queue , In this way, the nodes of each layer can be traversed from right to left . The value of the last node traversed by the breadth first search is the value of the lowest left node .

Code ：

class Solution {
    
public:
    int findBottomLeftValue(TreeNode* root) {
    
        int ret;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
    
            auto p = q.front();
            q.pop();
            if (p->right) {
    
                q.push(p->right);
            }
            if (p->left) {
    
                q.push(p->left);
            }
            ret = p->val;
        }
        return ret;
    }
};

Execution time ：8 ms, In all C++ Defeated in submission 81.05% Users of
Memory consumption ：21.1 MB, In all C++ Defeated in submission 62.89% Users of

author：LeetCode-Solution Add link description