Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return
[3,2,1].My Code is too long...
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
/* Magically, I implemented the morris traversal post order traversal version
private void swap(List res, int i, int j){
if(i == j)
return;
res.set( i, res.get(i) ^ res.get(j) );
res.set( j, res.get(i) ^ res.get(j) );
res.set( i, res.get(i) ^ res.get(j) );
}
private void reverseArrayList(List res, int i, int j){
while(i < j){
swap(res, i++, j--);
}
}
public List postorderTraversal(TreeNode root) {
TreeNode d = new TreeNode(-1);
// Error: forgot to put root to d.left.....
d.left = root;
List res = new ArrayList();
TreeNode c = d;
while(null != c){
if(null == c.left){
c = c.right;
continue;
}else{
TreeNode n = c.left;
// Error: null != n && c != n
// We shouldn't traverse n to c, should be before c.
while(null != n.right && c != n.right){
n = n.right;
}
if(null == n.right){
n.right = c;
c = c.left;
}else{
// c == n.right
// add the last element of left.right subtree
//res.add(n.val);
// add the last element of left subtree
// Error: There are two cases of n, n could be a left child node and right child node.
//if(c.left != n)
// res.add(c.left.val);
// Error: the above ones are wrong
// When tree were returned from the rightmost child, it will print a series of root node. following the return of the subtrees.
n = c.left;
int count = 0;
//Error: while( c != n.right), this time it is
// In this case, last element in this list is not added in.
while(c != n.right){
//printPathReverse(root.left, pre);
//we need a way to print the path reversely to do that.
//One way is to reverse this path like we reverse linklist.
res.add(n.val);
n = n.right;
count++;
}
res.add(n.val);
count++;
if(count > 1)
reverseArrayList(res, res.size() - count, res.size()-1);
n.right = null;
c = c.right;
}
}
// we can not put d != c in while condition, because it is initial condition
// Error: we don't need to add this here,
// we need this loop when c = d to add c.left child into result.
// Since d has no right child, and d is not a children of anybody, it will never be printed out
//if(c == d)
// return res;
}
return res;
}
*/
/* The second implementation is based on one stack, which stores all elements on the path from root to current node,
all we need to judge is the current node c is the left or right child of the top element of the stack.
if it is left child, we go right. (note, if it has no right child, we keep pop stack, i.e. the same behavior as it is right child)
if it is right child, we keep pop stack
public List postorderTraversal(TreeNode root) {
List res = new ArrayList();
if(null == root)
return res;
Stack st = new Stack();
TreeNode c = root;
while(true){
// null == c is not going to work anymore, we don't know if null is left or right.
if(null == c.left && null == c.right){
st.push(c);
while(!st.empty()){
c = st.pop();
res.add(c.val);
// Error: st.empty() should resides here.
if(st.empty())
return res;
TreeNode r = st.peek();
// Note: The same operation always hold for
// 1. c is the left child of r, and r.right is null
// 2. c is the right chiild of r.
// In both case, we track back to the path towards root.
// Therefore, when c is left child of r, and r.right is not null
// we loop into r.right
if(c == r.left && null != r.right){
c = r.right;
break;
}
}
}else if(null == c.left){
st.push(c);
c = c.right;
}else{
st.push(c);
c = c.left;
}
}
}
*/
// The third implementation is based on a previous node recorder to keep track of the direction of traversal flow.
// We need loop enviroment to maintain a clean program
// Without loop enviroment, there might be many conditional statements.
// This is the version we seperate the top of stack and c, i.e. top of stack is always one layer above c.
public List postorderTraversal(TreeNode root) {
List res = new ArrayList();
if(null == root)
return res;
TreeNode c = root;
TreeNode pre = null;
Stack st = new Stack();
while(true){
//System.out.println("c.val = " + c.val);
//System.out.println("pre.val = " + (null == pre? -1 : pre.val) );
//System.out.println("size = " + st.size());
if(null == pre || pre.left == c || pre.right == c){
// Moving downward, in this case, we try to keep dig down
if(null != c.left){
st.push(c);
pre = c;
c = c.left;
}else if(null != c.right){
st.push(c);
pre = c;
c = c.right;
}else{
pre = c;
if(st.empty()){
System.out.println("empty");
res.add(c.val);
return res;
}else{
c = st.pop();
}
}
}else{
// Moving upward
res.add(pre.val);
if(pre == c.right || (pre == c.left && null == c.right) ){
//System.out.println("Up");
pre = c;
if(st.empty()){
System.out.println("empty2");
res.add(c.val);
return res;
}else{
c = st.pop();
}
}else{
// pre == c.left
pre = c;
st.push(c);
c = c.right;
}
}
}
}
}
