[C++] Clean Code - DFS Recursion with Explanation


  • 2

    Imaging how we would find the max height of a tree. We can carry a max-height variable and keep updating it.
    With little change we can find the bottom-left as a byproduct of this process.

    The idea is to update the bottom-left only when the depth reach to the next level, that is, whenever you need to update max-height when height > max-height;

    Find Bottom Left

    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            int bottomLeft = 0;
            int height = 0;
            dfs(root, 1, height, bottomLeft);
            return bottomLeft;
        }
    
    private:
        void dfs(TreeNode* node, int depth, int& height, int& res) {
            if (!node) {
                return;
            }
            if (depth > height) {
                res = node->val;    // update res only when redefine the height
                height = depth;
            }
            dfs(node->left, depth + 1, height, res);
            dfs(node->right, depth + 1, height, res);
        }
    };
    

    Find Tree Height
    Here is how would you find the height of the tree in this approach, it is very similar to Find The Bottom Left

    class Solution {
    public:
        int treeHeight(TreeNode* root) {
            int height = 0;
            dfs(root, 1, height);
            return height;
        }
    
    private:
        void dfs(TreeNode* node, int depth, int& height) {
            if (!node) {
                return;
            }
            if (depth > height) {
                height = depth;
            }
            dfs(node->left, depth + 1, height);
            dfs(node->right, depth + 1, height);
        }
    };
    

Log in to reply
 

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