C++ recursive solution (beats 100%) with basic explanation


  • 4
    G

    Idea is simple:
    Keep track of the depth of the tree as you move along. Once you get out of left and right subtree of a node, update the leftVal. Code is quite self explanatory. I have added some basic documentation. I hope that it helps!

    class Solution {
    public:
        void findBottomLeftValue(TreeNode* root, int& maxDepth, int& leftVal, int depth) {
            if (root == NULL) {
                return;
            }
            //Go to the left and right of each node 
            findBottomLeftValue(root->left, maxDepth, leftVal, depth+1);
            findBottomLeftValue(root->right, maxDepth, leftVal, depth+1);
            
            //Update leftVal and maxDepth
            if (depth > maxDepth) {
                maxDepth = depth;
                leftVal = root->val;
            }
        }
        
        //Entry function
        int findBottomLeftValue(TreeNode* root) {
            int maxDepth = 0;
            //Initialize leftVal with root's value to cover the edge case with single node
            int leftVal = root->val;
            findBottomLeftValue(root, maxDepth, leftVal, 0);
            return leftVal;
        }
    };
    

  • 0
    N

    Thanks your idea, here is my Python version with the same idea

    class Solution(object):
        def helper(self, root, level):
            if not root:
                return None
            self.helper(root.left, level + 1)
            self.helper(root.right, level + 1)
            if level > self.max_level:
                self.max_level = level
                self.left_val = root.val
            
            
        def findBottomLeftValue(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.max_level=0
            self.helper(root, 1)
            return self.left_val
    

  • 0
    S

    my straightforward c++, dfs

    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            pair<int,int> result(root->val,1); //root!=null
            dfs(root,1,result);
            return result.first;
        }
    private:
        void dfs(TreeNode* root,int height,pair<int,int>& res)
        {
            if(!root->left && !root->right && height>res.second)
            {
                res = make_pair(root->val,height);
            }
            if(root->left) dfs(root->left,height+1,res);
            if(root->right) dfs(root->right,height+1,res);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.