DFS method, using two stacks, for TreeNode and the path sum


  • 0
    F

    Re: Could anyone offer me a non-recursive method?

    class Solution {
    public:
        int sumNumbers(TreeNode* root) {
            if(!root)
                return 0;
            stack<TreeNode*> s1;
            stack<int> s2;
            s1.push(root);
            s2.push(root->val);
            int sum=0,ret=0;
            while(!s1.empty()){
                TreeNode* node=s1.top();
                s1.pop();
                sum=s2.top();
                s2.pop();
                if(!node->left&&!node->right){
                    ret+=sum;
                }
                if(node->right){
                    s1.push(node->right);
                    s2.push(node->right->val + 10*sum);
                }
                if(node->left){
                    s1.push(node->left);
                    s2.push(node->left->val + 10*sum);
                }
            }
            return ret;
        }
    };
    
    

  • 0
    Y

    this is actually BFS, not DFS
    similar idea, it really doesn't matter whether we're using stack or queue

    public class Solution {
        public int sumNumbers(TreeNode root){
            if(root==null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            Queue<Integer> sum = new LinkedList<>();
            sum.offer(root.val);
            queue.offer(root);
            int res = 0;
            while(!queue.isEmpty()){
                TreeNode cur = queue.poll();
                int curVal = sum.poll();
                if(cur.left==null && cur.right==null){
                    res += curVal;
                    continue;
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                    sum.offer(curVal*10+cur.left.val);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                    sum.offer(curVal*10+cur.right.val);
                }
            }
            return res;
        }     
    }
    

Log in to reply
 

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