C++ DFS Solution with Simple Explanation

  • 0

    “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 {
        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;
            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.