Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
We know the elements can be printed post-order easily using recursion, as follow:
|
1
2
3
4
5
6
|
voidpostOrderTraversal(BinaryTree *p){
if(!p)return;
postOrderTraversal(p->left);
postOrderTraversal(p->right);
cout<<p->data;
}
|
Hint:
As usual, a stack-based solution is necessary when there is no parent pointer available in the tree. Try to follow the post-order traversal of a sample binary tree. When should you print a node’s value? Note under what condition it traverses up/down the tree. Try to use a variable to store the previously-traversed node. How would it help when it traverses up/down the tree?
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.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
voidpostOrderTraversalIterative(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);
}elseif(curr->right){
s.push(curr->right);
}else{
cout<<curr->data<<" ";
s.pop();
}
}
// we are traversing up the tree from the left
elseif(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
elseif(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. We could refactor out the redundant code, and now it appears to be more concise. Note how the code section for printing curr‘s value get refactored into one single else block. Don’t worry about in an iteration where its value won’t get printed, as it is guaranteed to enter the else section in the next iteration.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
voidpostOrderTraversalIterative(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);
elseif(curr->right)
s.push(curr->right);
}elseif(curr->left==prev){
if(curr->right)
s.push(curr->right);
}else{
cout<<curr->data<<" ";
s.pop();
}
prev=curr;
}
}
|
Alternative Solution:
An alternative solution is to use two stacks. Try to work it out on a piece of paper. I think it is quite magical and beautiful. You will think that it works magically, but in fact it is doing a reversed pre-order traversal. That is, 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.
Here is how it works:
- 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.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
voidpostOrderTraversalIterativeTwoStacks(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();
}
}
|
Complexity Analysis:
The two-stack solution takes up more space compared to the first solution using one stack. In fact, the first solution has a space complexity of O(h), where h is the maximum height of the tree. The two-stack solution however, has a space complexity of O(n), where n is the total number of nodes.
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public ArrayList<Integer> postorderTraversal(TreeNode root) { 12 // IMPORTANT: Please reset any member data you declared, as 13 // the same Solution instance will be reused for each test case. 14 Stack<TreeNode> st = new Stack<TreeNode>(); 15 Stack<Integer> output = new Stack<Integer>(); 16 ArrayList<Integer> result = new ArrayList<Integer>(); 17 if(root == null) return result; 18 st.push(root); 19 while(!st.isEmpty()){ 20 TreeNode tmp = st.pop(); 21 output.push(tmp.val); 22 if(tmp.left != null) st.push(tmp.left);// 这里是先left 再right， 而 preorder 是先right 再left 23 if(tmp.right != null) st.push(tmp.right); 24 } 25 while(!output.isEmpty()){ 26 result.add(output.pop()); 27 } 28 return result; 29 } 30 }
或者：
1 public class Solution { 2 /** 3 * @param root: The root of binary tree. 4 * @return: Postorder in ArrayList which contains node values. 5 */ 6 public ArrayList<Integer> postorderTraversal(TreeNode root) { 7 // write your code here 8 LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); 9 ArrayList<Integer> result = new ArrayList<Integer>(); 10 if(root == null) return result; 11 TreeNode prev = null; 12 stack.push(root); 13 while(!stack.isEmpty()){ 14 TreeNode cur = stack.peek(); 15 if(prev == null || prev.left == cur || prev.right == cur){ 16 if(cur.left != null){ 17 stack.push(cur.left); 18 }else if(cur.right != null){ 19 stack.push(cur.right); 20 } 21 } 22 else if(cur.left == prev){ 23 if(cur.right != null){ 24 stack.push(cur.right); 25 } 26 }else{ 27 cur = stack.pop(); 28 result.add(cur.val); 29 } 30 prev = cur; 31 } 32 return result; 33 } 34 }