http://leetcode.com/2010/10/binary-tree-post-order-traversal.html
Given a binary tree, return the postorder traversal of its nodes' values.
For the iterative and Morris Traversal ones, things become a bit complicated.
Solution:
We use a prev variable to keep track of the previously-traversed node. Let’s assume curr is the current node that’s on top of the stack. When prev is curr‘s parent, we are traversing down the tree. In this case, we try to traverse to curr‘s left child if available (ie, push left child to the stack). If it is not available, we look at curr‘s right child. If both left and right child do not exist (ie, curr is a leaf node), we print curr‘s value and pop it off the stack.
If prev is curr‘s left child, we are traversing up the tree from the left. We look at curr‘s right child. If it is available, then traverse down the right child (ie, push right child to the stack), otherwise print curr‘s value and pop it off the stack.
If prev is curr‘s right child, we are traversing up the tree from the right. In this case, we print curr‘s value and pop it off the stack.
http://codesniper.blogspot.com/2015/04/145-binary-tree-postorder-traversal.html
we have to push both left and right to stack. Obviously, if current node's left is not null, we push its left, if cur's right is not null, we have to check if the cur'right has been processed, if so, output cur.
(1) Push the root node into the stack.
(2) while the stack is not empty, do:
if
the top node is a leaf node (no left&right children), pop it.
or if the top node has been visited, pop it. (here we use a sign head to show the latest popped node, if the top node's child = the latest popped node, either left or right, it must has been visited.)
else
b. push the right child of the top node (if exists)
c. push the left child of the top node (if exists)
EPI BinaryTreePostorderTraversalIterative.java
invertedPreOrderTraversal BinaryTreePostorderTraversalIterativeAlternative.java
http://blog.csdn.net/linhuanmars/article/details/22009351
http://www.danielbit.com/blog/puzzle/leetcode/leetcode-binary-tree-postorder-traversal
Alternative Solution: Using Two Stacks, print post-order reversely first: O(n) space
The order of traversal is a node, then its right child followed by its left child. This yields post-order traversal in reversed order. Using a second stack, we could reverse it back to the correct order.
Push the root node to the first stack.
Pop a node from the first stack, and push it to the second stack.
Then push its left child followed by its right child to the first stack.
Repeat step 2) and 3) until the first stack is empty.
Once done, the second stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the second stack one by one and you’re done.
If you keep visited flags in the binary tree while traversing, the problem could be solved in a more direct manner.
we can ' push left child from root until left most leaf into stack. then start pop node from the stack, however, if the current node which going to be pop out has right node we should start push all left nodes of the right child until to leaf.
http://leetcode0.blogspot.com/2013/11/binary-tree-postorder-traversal.html
http://en.wikipedia.org/wiki/Tree_traversal#Post-order_2
Recursive Version
From http://leetcode.com/2010/10/binary-tree-post-order-traversal.html
Post-order traversal is useful in some types of tree operations:
Tree deletion. In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node can only be deleted when both of its left and right subtrees are deleted.
Evaluating post-fix notation.
If you keep visited flags in the binary tree while traversing, the problem could be solved in a more direct manner.
Post-order traversal is useful in some types of tree operations:
Given a binary tree, return the postorder traversal of its nodes' values.
For the iterative and Morris Traversal ones, things become a bit complicated.
Solution:
We use a prev variable to keep track of the previously-traversed node. Let’s assume curr is the current node that’s on top of the stack. When prev is curr‘s parent, we are traversing down the tree. In this case, we try to traverse to curr‘s left child if available (ie, push left child to the stack). If it is not available, we look at curr‘s right child. If both left and right child do not exist (ie, curr is a leaf node), we print curr‘s value and pop it off the stack.
If prev is curr‘s left child, we are traversing up the tree from the left. We look at curr‘s right child. If it is available, then traverse down the right child (ie, push right child to the stack), otherwise print curr‘s value and pop it off the stack.
If prev is curr‘s right child, we are traversing up the tree from the right. In this case, we print curr‘s value and pop it off the stack.
void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
// we are traversing down the tree
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the left
else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the right
else if (curr->right == prev) {
cout << curr->data << " ";
s.pop();
}
prev = curr; // record previously traversed node
}
}
void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
prev = curr;
}
}
Iterative Versionhttp://codesniper.blogspot.com/2015/04/145-binary-tree-postorder-traversal.html
we have to push both left and right to stack. Obviously, if current node's left is not null, we push its left, if cur's right is not null, we have to check if the cur'right has been processed, if so, output cur.
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<Integer>();
if(root==null) return res;
Stack<TreeNode> st=new Stack<TreeNode>();
TreeNode pre=null;
while(root!=null || !st.isEmpty()){
if(root!=null){
st.push(root);
root=root.left;
}
else{
if(st.peek().right==null || st.peek().right==pre){
pre=st.pop();
res.add(pre.val);
}
else { root=st.peek().right; }
}
} (1) Push the root node into the stack.
(2) while the stack is not empty, do:
if
the top node is a leaf node (no left&right children), pop it.
or if the top node has been visited, pop it. (here we use a sign head to show the latest popped node, if the top node's child = the latest popped node, either left or right, it must has been visited.)
else
b. push the right child of the top node (if exists)
c. push the left child of the top node (if exists)
vector<int> postorderTraversal(TreeNode *root) { stack<TreeNode*> st; vector<int> res; if (!root){return res;} st.push(root); TreeNode* head=root; while (!st.empty()){ TreeNode* top = st.top(); if ((top->left==NULL && top->right==NULL)||top->right==head || top->left==head){ res.push_back(top->val); st.pop(); head = top; }else{ if (top->right!=NULL){st.push(top->right);} if (top->left!=NULL){st.push(top->left);} } } return res; }invertedPreOrderTraversal BinaryTreePostorderTraversalIterativeAlternative.java
http://blog.csdn.net/linhuanmars/article/details/22009351
http://www.danielbit.com/blog/puzzle/leetcode/leetcode-binary-tree-postorder-traversal
Alternative Solution: Using Two Stacks, print post-order reversely first: O(n) space
The order of traversal is a node, then its right child followed by its left child. This yields post-order traversal in reversed order. Using a second stack, we could reverse it back to the correct order.
Push the root node to the first stack.
Pop a node from the first stack, and push it to the second stack.
Then push its left child followed by its right child to the first stack.
Repeat step 2) and 3) until the first stack is empty.
Once done, the second stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the second stack one by one and you’re done.
void postOrderTraversalIterativeTwoStacks(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
stack<BinaryTree*> output;
s.push(root);
while (!s.empty()) {
BinaryTree *curr = s.top();
output.push(curr);
s.pop();
if (curr->left)
s.push(curr->left);
if (curr->right)
s.push(curr->right);
}
while (!output.empty()) {
cout << output.top()->data << " ";
output.pop();
}
}
If you keep visited flags in the binary tree while traversing, the problem could be solved in a more direct manner.
We use a prev variable to keep track of the previously-traversed node. Let’s assume curr is the current node that’s on top of the stack. When prev is curr‘s parent, we are traversing down the tree. In this case, we try to traverse to curr‘s left child if available (ie, push left child to the stack). If it is not available, we look at curr‘s right child. If both left and right child do not exist (ie, curr is a leaf node), we print curr‘s value and pop it off the stack.
If prev is curr‘s left child, we are traversing up the tree from the left. We look at curr‘s right child. If it is available, then traverse down the right child (ie, push right child to the stack), otherwise print curr‘s value and pop it off the stack.
If prev is curr‘s right child, we are traversing up the tree from the right. In this case, we print curr‘s value and pop it off the stack. - O(h) space
void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
// we are traversing down the tree
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the left
else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the right
else if (curr->right == prev) {
cout << curr->data << " ";
s.pop();
}
prev = curr; // record previously traversed node
}
}
The above method is easy to follow, but has some redundant code.
void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
prev = curr;
}
}
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); // Used to restore parents
stack.push(root);
TreeNode q = null;
while (!stack.isEmpty()) {
TreeNode p = stack.peek();
if (q == null || p == q.left || p == q.right) { // Traverse downwards
if (p.left == null && p.right == null) { // Current node is a leaf; access it
result.add(p.val);
stack.pop();
} else { // Current node is not a leaf; consider its left child if any, or its right child
if (p.left != null)
stack.push(p.left);
else
stack.push(p.right);
}
} else if (p.left == q) { // Traverse backwards, and previous node is current node's left child
if (p.right == null) { // Current node has no right child; access it
result.add(p.val);
stack.pop();
} else { // Current node has right child; consider the right child
stack.push(p.right);
}
} else { // Traverse backwards, and previous node is current node's right child; access it
result.add(p.val);
stack.pop();
}
q = p;
}
return result;
}
http://rleetcode.blogspot.com/2014/06/binary-tree-postorder-traversal.htmlwe can ' push left child from root until left most leaf into stack. then start pop node from the stack, however, if the current node which going to be pop out has right node we should start push all left nodes of the right child until to leaf.
Using Visited Hashset:public List<Integer> postorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();if (root == null){return result;}Stack<TreeNode> stack =new Stack<TreeNode> ();LinkedList<TreeNode> visitedList= new LinkedList<TreeNode> ();while(root!=null){stack.push(root);root=root.left;}while(!stack.isEmpty()){TreeNode current = stack.peek();if (current.right == null || visitedList.contains(current)){result.add(current.val);stack.pop();if (visitedList.contains(current)){visitedList.remove(current);}}else{visitedList.add(current);root=current.right;while (root!=null){stack.push(root);root=root.left;}}}return result;}
http://leetcode0.blogspot.com/2013/11/binary-tree-postorder-traversal.html
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList(); if(root ==null) return result; Stack<TreeNode> stack = new Stack(); Set<TreeNode> set = new HashSet(); stack.push(root); set.add(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); if(set.contains(node)){// first time to find this node stack.push(node); if(node.right!=null){ stack.push(node.right); set.add(node.right); } if(node.left!=null){ stack.push(node.left); set.add(node.left); } set.remove(node); }else{// node should be printed directly result.add(node.val); } }// end of while return result; }public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result=new ArrayList<Integer>();if (root==null){return result;}Stack<TreeNode> stack=new Stack<TreeNode>();TreeNode runner=root;while (runner!=null){stack.push(runner);runner=runner.left;}// child node used to record if mid node's child has been visited inorder to tell if need to pop out//the mid nodeTreeNode child=null;while (!stack.isEmpty()){TreeNode current=stack.peek();if (current.right==null || current.right==child){result.add(stack.pop().val);// catch the child node, inorder mid node could check if its child already be visitedchild=current;}else{current=current.right;while (current!=null){stack.push(current);current=current.left;}}}return result;}
http://en.wikipedia.org/wiki/Tree_traversal#Post-order_2
iterativePostorder(node)
parentStack = empty stack
lastnodevisited = null
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
parentStack.push(node)
node = node.left
else
peeknode = parentStack.peek()
if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right)
/* if right child exists AND traversing node from left child, move right */
node = peeknode.right
else
parentStack.pop()
visit(peeknode)
lastnodevisited = peeknode
Morris Traversal
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode p = dummy, q = null;
while (p != null) {
if (p.left == null) {
p = p.right;
} else {
// Find in-order predecessor of current node
q = p.left;
while (q.right != null && q.right != p)
q = q.right;
if (q.right == null) { // Its left subtree has not been traversed; link it to its predecessor
q.right = p;
p = p.left;
} else {
// Its left subtree has been traversed; add the numbers from p's left child to its in-order
// predecessor in reverse order, and recover tree structure
reverse(p.left, q);
TreeNode temp = q;
while (temp != p.left) {
result.add(temp.val);
temp = temp.right;
}
result.add(temp.val);
reverse(q, p.left);
q.right = null;
p = p.right;
}
}
}
return result;
}
private void reverse(TreeNode from, TreeNode to) {
if (from == to)
return;
TreeNode q = from, p = from.right;
while (q != to) {
TreeNode next = p.right;
p.right = q;
q = p;
p = next;
}
}
Recursive Version
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
recursivePreorderTraversal(root, result);
return result;
}
private void recursivePreorderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root == null)
return;
recursivePreorderTraversal(root.left, result); // Traverse the left subtree
recursivePreorderTraversal(root.right, result); // Traverse the right subtree
result.add(root.val); // Access the value of current node
}
From http://leetcode.com/2010/10/binary-tree-post-order-traversal.html
Post-order traversal is useful in some types of tree operations:
Tree deletion. In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node can only be deleted when both of its left and right subtrees are deleted.
Evaluating post-fix notation.
If you keep visited flags in the binary tree while traversing, the problem could be solved in a more direct manner.
Post-order traversal is useful in some types of tree operations:
Tree deletion. In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node can only be deleted when both of its left and right subtrees are deleted.
Evaluating post-fix notation.
http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
Read full article from LeetCode - Binary Tree Postorder Traversal | Darren's Blog
Evaluating post-fix notation.
http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
The idea is to move down to leftmost node using left pointer. While moving down, push root and root’s right child to stack. Once we reach leftmost node, print it if it doesn’t have a right child. If it has a right child, then change root so that the right child is processed before.
Following is detailed algorithm.
1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
static Node root; ArrayList<Integer> list = new ArrayList<Integer>(); // An iterative function to do postorder traversal of a given binary tree ArrayList<Integer> postOrderIterative(Node node) { Stack<Node> S = new Stack<Node>(); // Check for empty tree if (node == null) { return list; } S.push(node); Node prev = null; while (!S.isEmpty()) { Node current = S.peek(); /* go down the tree in search of a leaf an if so process it and pop stack otherwise move down */ if (prev == null || prev.left == current || prev.right == current) { if (current.left != null) { S.push(current.left); } else if (current.right != null) { S.push(current.right); } else { S.pop(); list.add(current.data); } /* go up the tree from left node, if the child is right push it onto stack otherwise process parent and pop stack */ } else if (current.left == prev) { if (current.right != null) { S.push(current.right); } else { S.pop(); list.add(current.data); } /* go up the tree from right node and after coming back from right node process parent and pop stack */ } else if (current.right == prev) { S.pop(); list.add(current.data); } prev = current; } return list; }