Share my two C++ solutions,easy to understand


  • 0
    V

    Solution (1): Recursion

    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            if (root == NULL)
                return 0;
            
            return recursionSum(root, 0, 0);
        }
        
        int  recursionSum(TreeNode *root, int sum, int total)
        {
            if (root == NULL)
                return total;
            
            if (root != NULL)
                sum = sum * 10 + root->val;
                
            if (root->left == NULL && root->right == NULL)
            {
                total += sum;
                return total;
            }
            
            return recursionSum(root->left, sum, total) + recursionSum(root->right, sum, total);
        }
    };
    

    Solution (2):Iteration

    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            if (root == NULL)
                return 0;
            
            int total = 0, curSum = 0;
            stack<TreeNode *> s;
            unordered_map<TreeNode*, int> visited;
            TreeNode *temp = NULL;
            
            s.push(root);
            curSum = curSum * 10 + root->val;
            visited[root] = 1;
            
            while (!s.empty())
            {
                temp = s.top();
    
                if (temp->left != NULL && visited[temp->left] != 1)
                {
                    s.push(temp->left);
                    curSum = curSum * 10 + temp->left->val; 
                    visited[temp->left] = 1;
                    continue;
                }
    
                if (temp->right != NULL && visited[temp->right] != 1)
                {
                    s.push(temp->right);
                    curSum = curSum * 10 + temp->right->val; 
                    visited[temp->right] = 1;
                    continue;
                }
                
                if (temp->left == NULL && temp->right == NULL)
                    total += curSum;
                
                s.pop();
                curSum = (curSum - temp->val) / 10;
            }
            
            return total;
        }
    };

Log in to reply
 

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