c++ soln that uses stack instead of recursive call.

  • 0

    The basic idea here is to use std::stack structure instead of recursion for the dfs, runtime is 3ms.

    class Solution {
        int sumNumbers(TreeNode* root) {
            if(root == NULL) return 0;
            int pathNum = 0;    //will store the current path value of a node
            stack< tuple<TreeNode*, int > > mStack;
            mStack.push(tuple<TreeNode*, int >(root, pathNum));
            tuple<TreeNode*, int > tempT;
            TreeNode* temp = NULL;
            int sum = 0;
            // using stack for dfs
                tempT = mStack.top();
                temp = get<0>(tempT);
                pathNum = get<1>(tempT);
                pathNum = pathNum*10 + temp->val;
                if(temp->left== NULL && temp->right == NULL) {
                    sum += pathNum;
                if(temp->left !=NULL) mStack.push( tuple<TreeNode*, int>(temp->left, pathNum));
                if(temp->right != NULL) mStack.push( tuple<TreeNode*, int>(temp->right, pathNum));
            return sum;

Log in to reply

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