Lexi's Leetcode solutions

[leetcode] PathSum | 找从root到leaft的加和==x的路径是否存在[iteratively]

Posted on: August 4, 2013

想练习translate recursion to iteration,的确很难。。本来是这么想的:

stack.push(root);
while (!empty(stack)) {
   Node node = stack.pop();
   check if node is leaf, if so, compare curr sum to x, if not equals x, then currsum -= leaf.val
   else
      node.push(node.right);
      node.push(node.left);
}
   a
  / \
 b   c
/ \
d  e

然后就悲剧了。这样的话,比如上面的数,到e了,pop出e, 但是currSum只减去了e的值,b的值还留着,然后就pop c了,所以右边就永久的留下了b的值在currSum里面。怎么能知道“该pop parent”了呢?显然要一路pop出去的话,还得套个循环。另外别每次把左右两枝都push进去,一次push一个就好了。这样stack里面永远是一条valid的path。

while (!empty(stack)) {
    Node node = stack.peak();
    if (node.left exists)
       stack.push(node.left);
       currSum += node.left.val;
    } else if (node.right exists)
       do the same for right node
    } else {
       // this is a leaf now, you want to 
       1.看currSum是不是符合,不符合的话,这个leaf就得出去了
       2.看要不要把parent一起pop出去
       if (currSum == x)
          return true;
       Node child = stack.pop();
       currSum -= child.val;
       while (stack is not empty) {
         Node parent = stack.peek();
         if (child is parent's left && parent has no right || child is parent's right) {
            //说明这一支已经结束,parent也改闪了。
            stack.pop();
            currSum -= parent.val;
            child = parent;
         } else {
            //说明这一支还没结束,parent的右孩子还没处理,所以把右孩子push进去,path改了方向。
            stack.push(parent.right);
            currSum += parent.right.val;
            break;
         }
    }
}
          
          

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: