Archive for August 4th, 2013
经典中的经典。
前序 pre order （中左右）：
- push root
- pop，若有right, push right，若有left push left
- 这样继续一边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 （左中右）：
- push root左支到死
- pop， 若pop的有right，则把right当root对待push它的左支到死。
- 这样继续一边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;
}
Tags: converToIteration, tree
想练习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;
}
}
}
本来觉得是弱智题，但是基本从来不top down的做树的题，写完还真挂在bug上了。
top down利用leaf的树题一般是这样的pattern:
void topDown(Node node) {
if (node == null)
//this means reaching a branch that only one side has something, the other side is this (null)
if (node.left == null && root.right == null)
//this is leaf, do something, then return;
topDown(node.left);
topDown(node.right);
}
和平时做的preorder（中左右）的区别：preOrder这种遍历下来，的确会在empty node的时候停，但是不能判断什么时候到了叶子节点。而topDown利用了叶子节点的定义来判断当前节点是否叶子，可以这时候做一些运算。
void preOrder(Node node) {
if (node == null)
//this could either mean parent is a leaf, or parent's this branch is empty but has another child
}
preOrder(node.left);
preOrder(node.right);
}
Lexi's Leetcode solutions 