Recursion Traversal
It is easy to recursively traverse a tree.
1.Preorder: root->left->right
public traverse(TreeNode root){
visit(root);
traverse(root.left);
traverse(root.right);
}
2.Postorder: left->right->root
public traverse(TreeNode root){
traverse(root.left);
traverse(root.right);
visit(root);
}
3.Inorder traverse: left->root->right
public traverse(TreeNode root){
traverse(root.left);
visit(root);
traverse(root.right);
}
Non-recursion Traversal
When implementing traversal using the non-recursive method, we might need some extra space (stack) to store some tree nodes. Morris Inorder Traversal presents a method to traverse a binary tree using O(1) space and O(n) time.
1.Preorder: root->left->right
Considering stack is the first-in-last-out Container, we should push the right node into stack before the left node so that the left node can be popped and visited earlier. //pop root, push right, push left
public traverse(TreeNode root){
if(root==null) return ;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop(); //visit the node
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
}
2.Postorder: left->right->root
Postorder is similar the preorder, but "first pop the root, then push the left, then push the right". So the visiting is like "root, right, left". In the end, reverse the sequence, we can get "left, right, root".
public traverse(TreeNode root){
if(root==null) return ;
Stack<TreeNode> stack = new Stack<>();
List<TreeNode> list = new ArrayList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
list.add(node);
if(node.left!=null) stack.push(node.left);
if(node.right!=null) stack.push(node.right);
}
for(int i = list.size()-1;i>=0;i--){
visit(list.get(i));
}
}
3.Inorder traverse: left->root->right
public traverse(TreeNode root){
if(root==null) return ;
Stack<TreeNode> stack = new Stack<>();
List<TreeNode> list = new ArrayList<>();
TreeNode cur = root;
while(true){
if(root.left!=null){
stack.push(root);
cur = cur.left;
}else{
if(stack.isEmpty()){
break;
}else{
TreeNode parent = stack.pop(); //visit the node now
cur = parent.right;
}
}
}
}
Morris Inorder Traverse
public traverse(TreeNode root){
if(root==null) return ;
TreeNode cur = root;
while(cur!=null){
if(cur.left==null){ //visit the right node next;
visit(cur);
cur = cur.right;
}else{
TreeNode predecessor = cur.left;
//find the Predecessor of the cur node.
while(predecessor.right!=null && predecessor.right!=cur) predecessor = predecessor.right;
if(predecessor.right==null){
//have not visited cur node's left tree, build the blue link in the graph
predecessor.right = cur;
cur = cur.left;
}else{
//have visited cur node's left tree, remove the blue link in the graph
predecessor.right = null;
visit(cur);
cur = cur.right;
}
}
}
}
