A DFS based C++ solution


  • 1
    D
    class Solution {
    public:
        int sumNumbers(TreeNode *root) {
            total = 0;
            findLeaf(root, 0);
            return total;
        }
    private:
        int total;
        void findLeaf(TreeNode *root, int val) {
            if(!root) return; /// no need to worry about null subtree of a nonleaf node;
            val = val*10 + root->val;
            /// add the result of one leaf to the total;
            if(!root->left && !root->right){
                total += val;
                return;
            }
            //// if not leaf, pass val to subtrees;
            findLeaf(root->left, val);
            findLeaf(root->right, val);
        }
    };
    

    This solution is based on the observation that only when the value reaches a leaf, it should be add to the global total. Before that, it could be passed on with

    val = val*10 + root->val;


  • 0
    W

    Hi, shares the same idea:)


Log in to reply
 

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