Lexi's Leetcode solutions

Posts Tagged ‘converToIteration

用两个stack O(n)的方法:

  1. 一个stack s1 push root。
  2. 一边pop s1进s2,一边把pop的left, right push进s1(先左后右,这先进s2的是右边,左边在s2靠前部分,所以最后先print出来)
  3. 这样最后s2就是一个正好从上到下是post order的traversal,一边pop一边print就行了。
public void postOrderTwoStacks(TreeNode root) {
  Stack<TreeNode> s1 = new Stack<TreeNode>();
  Stack<TreeNode> s2 = new Stack<TreeNode>();
  s1.push(root);
  while (!s1.isEmpty()) {
    TreeNode pop = s1.pop();
    s2.push(pop);
    if (pop.left != null)
      s1.push(pop.left);
    if (pop.right != null)
      s1.push(pop.right);
  }
  while (!s2.isEmpty()) {
    System.out.print(s2.pop().val + ", ");
  }
}

用一个stack O(h)的方法:

  1. 一个stack,先push root
  2. keep一个prev variable表示刚才试过的node(在stack里尝试来着,不管最后是否把它pop出去了),一直在更新。
  3. stack.peek() == curr,每次用curr和prev比较
    • 如果prev是空或者prev是curr的parent,说明在top down的traverse,这时候可不能print prev(那就变成preorder了);而应该push curr的左子,木有才push右子,全都木有说明curr是leaf,就pop print就行了。
    • 如果prev是curr的左子,说明在从左下角往上traverse,这时若curr有右子,则push右子(应该traverse右子)- prev应该是已经pop出来的了。
    • 如果prev是curr的右子,说明从右下角往左上traverse,这时直接pop print curr就行了,因为这时root也该出来了。
public void postOrder(TreeNode root) {
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  TreeNode prev = null;
  while (!s.isEmpty()) {
    TreeNode curr = s.peek();
    if (prev == null || prev.left == curr || prev.right == curr) { // top down
      if (curr.left != null)
        s.push(curr.left);
      else if (curr.right != null)
        s.push(curr.right);
      else {// is leaf
        popAndPrint(s, curr);
      }
    } else if (prev == curr.left) { // from left child to parent
      if (curr.right != null)
        s.push(curr.right);
      else {
        popAndPrint(s, curr);
      }
    } else { // prev.right == curr, from right child to parent
      popAndPrint(s, curr);
    }
    prev = curr;
  }
}
private void popAndPrint(Stack<TreeNode> s, TreeNode curr) {
  System.out.print(curr.val + ", ");
  s.pop();
}
Advertisements

经典中的经典。

前序 pre order (中左右):

  1. push root
  2. pop,若有right, push right,若有left push left
  3. 这样继续一边pop一边push。直到stack为空。
public void preOrder(TreeNode root) {
  if (root == null)
    return;
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  while (!s.isEmpty()) {
    TreeNode top = s.pop();
    System.out.print(top.val + ", ");
    if (top.right != null)
      s.push(top.right);
    if (top.left != null)
      s.push(top.left);
  }
}

中序 in order (左中右):

  1. push root左支到死
  2. pop, 若pop的有right,则把right当root对待push它的左支到死。
  3. 这样继续一边pop一边push。直到stack为空。
public void inOrder(TreeNode root) {
  if (root == null)
    return;
  Stack<TreeNode> s = new Stack<TreeNode>();
  pushAllTheyWayAtLeft(s, root);
  while (!s.isEmpty()) {
    TreeNode top = s.pop();
    System.out.print(top.val + ", ");
    if (top.right != null)
      pushAllTheyWayAtLeft(s, top.right);
  }
}
private void pushAllTheyWayAtLeft(Stack<TreeNode> s, TreeNode root) {
  while (root != null) {
    s.push(root);
    root = root.left;
  }
}

another way: keep a curr pointer, when curr is null means reached the left most, then start popping

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                result.add(curr.val);
                curr = curr.right;
            }
        }
        return result;
    }

想练习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;
         }
    }
}