Li Kou today's question 513 Find the value in the lower left corner of the tree

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

The idea is simple , Traverse the left and right subtrees respectively （ The former sequence traversal ）, The first node encountered when reaching the maximum depth is The bottom and the left The node of .

Set a variable maxDepth Used to record Trees The maximum depth of , Set another variable depth To record the current traversal depth , The initial values of both values are set to 0, Set up a tree node , Used to save the result node .

In the process of recursive traversal , If you find the depth of the current traversal depth Be greater than maxDepth The maximum depth of , Then give it to me maxDepth assignment , Make sure its data is always updated , And always the biggest . At the same time let res Always point to the deepest node .

class Solution {
    // Record the maximum depth of the tree 
    int maxDepth = 0;
    // Record traverse  The depth traversed recursively 
    int depth = 0;
    // Result node , It is used to save the bottom left node 
    TreeNode res = null;

    public int findBottomLeftValue(TreeNode root) {
        traverse(root);
        return res.val;
    }

    
    void traverse(TreeNode root){
        if(root == null){
            return ;
        }
        // The position of preorder traversal 
        depth++;
        if(depth > maxDepth){
            // When the maximum depth is reached , The first node encountered is the bottom left node 
            maxDepth = depth;
            res = root;
        }
        traverse(root.left);
        traverse(root.right);
        // Postorder traversal position , Return to root node , Traverse depth minus one 
        depth--;
​
    }
​
}