C++ DFS Solution with Simple Explanation


  • 0
    F

    “The leftmost value in the last row of the tree” must be a leaf node, so we can carry out depth first search and record the first leaf value of one specific layer. When depth grows, update the {depth, value} pair.

    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            pair<int, int> dv = {-1, INT_MIN};
            dfs(root, dv, 0);
            
            return dv.second;
        }
        // dv: depth and value pair
        void dfs(TreeNode* root, pair<int, int>& dv, int depth) {
            if (root == NULL) return ;
            if (root->left == NULL && root->right == NULL && dv.first < depth) {
                dv.first = depth;
                dv.second = root->val;
                return;
            }
            else {
                dfs(root->left, dv, depth + 1);
                dfs(root->right, dv, depth + 1);
            }
        }
    };
    

Log in to reply
 

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