Leetcode-513: find the lower left corner value of the tree

513. Find the value in the lower left corner of the tree

Title Description ：
Given the root node of a binary tree 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 .
What needs to be grasped is in the question Leftmost It means , Because it's the leftmost , Therefore, according to the requirements of the topic, the node we seek is not necessarily the left leaf node , It may also be the deepest right leaf , Here are a few examples and their results

According to the above diagram, we can easily know that the solution goal is The value of the deepest leftmost node of the tree . There are generally two directions for solving this kind of problem ： Depth first and breadth first , Generally speaking, for solving problems involving levels , Breadth first has clearer logic . Let's analyze and solve the problem from two perspectives .

Depth first DFS（O(N),O(N)）

Depth first is achieved by recursion based on preorder traversal . To facilitate hierarchical comparison, we use a reference parameter curdepth To record The level of the leftmost value that has been calculated Easy update iteration . In addition, use depth To represent the level of the current node , To ensure the correctness of backtracking （ Do not interfere with the deep update of other nodes ）,depth It needs to be set as a normal parameter .

class Solution {
    
public:
    //  among num Is the value that needs to be recorded ,depth Is the depth of the currently accessed tree node 
    // curdepth Is the depth of the node corresponding to the saved return value 
    void getLeft(TreeNode* root, int &num,int depth,int &curdepth){
    
        if(root == nullptr) return;
        //  Save the leftmost element of each layer 
        if(root->left == nullptr && root->right == nullptr){
    
            // depth>curdepth It means that the current node is the leftmost node of this layer 
            if(depth > curdepth){
    
                curdepth = depth;
                num = root->val;
            }
        }
        getLeft(root->left,num,depth+1,curdepth);
        getLeft(root->right,num,depth+1,curdepth); 
    }
    int findBottomLeftValue(TreeNode* root) {
    
        int n = root->val;
        int dep = 0;
        if(!root->left && !root->right) return n;
        getLeft(root,n,1,dep);
        return n;
    }
};

breadth-first BFS（O(N),O(1)）

It is relatively simple to solve the problem of breadth first , You only need to save it when you enter a new layer for the first time Team leader It is the node value of the leftmost element of this layer .

class Solution {
    
public:
    int findBottomLeftValue(TreeNode* root) {
    
        //  If only the root node , Return the value of the root node 
        if(!root ->left && !root->right) return root->val;
        //  Level traversal 
        queue<TreeNode*> que;
        que.push(root);
        //  Initialization return value 
        int res = 0;
        //  Access breadth traverses the queue 
        while(!que.empty()){
    
            size_t size = que.size();
            TreeNode* node = nullptr;
            //  Take the leftmost element of each layer 
            res = que.front()->val;
            //  Process elements by layer 
            while(size--){
    
                node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        //  Return results 
        return res;
    }
};