Created
March 29, 2014 01:23
-
-
Save jingz8804/9846546 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for binary tree | |
* public class TreeNode { | |
* int val; | |
* TreeNode left; | |
* TreeNode right; | |
* TreeNode(int x) { val = x; } | |
* } | |
*/ | |
import java.util.Stack; | |
public class PostOrderTraversal { | |
private class NodeInfo{ | |
TreeNode node; | |
boolean isLeftVisited; | |
boolean isRightVisited; | |
public NodeInfo(TreeNode node){ | |
this.node = node; | |
isLeftVisited = false; | |
isRightVisited = false; | |
if(node.left == null) isLeftVisited = true; | |
if(node.right == null) isRightVisited = true; | |
} | |
} | |
public ArrayList<Integer> postorderTraversal(TreeNode root) { | |
ArrayList<Integer> result = new ArrayList<Integer>(); | |
if(root == null) return result; | |
Stack<NodeInfo> stack = new Stack<NodeInfo>(); | |
NodeInfo rNode = new NodeInfo(root); | |
stack.push(rNode); | |
while(stack.size() > 0){ | |
// peep at the top node | |
NodeInfo n = stack.peek(); | |
// if left side exists and is unvisited, go visit | |
if(n.node.left != null && n.isLeftVisited == false){ | |
n.isLeftVisited = true; | |
visitSubTree(new NodeInfo(n.node.left), stack, result); | |
}// else if right side exists and is unvisited, go visit | |
else if(n.node.right != null && n.isRightVisited == false){ | |
n.isRightVisited = true; | |
visitSubTree(new NodeInfo(n.node.right), stack, result); | |
}// else if both sides are visited, pop it | |
else if(n.isLeftVisited == true && n.isRightVisited == true){ | |
result.add(n.node.val); | |
stack.pop(); | |
} | |
} | |
return result; | |
} | |
private void visitSubTree(NodeInfo n, Stack<NodeInfo> stack, ArrayList<Integer> result){ | |
while(isLeafNode(n) == false){ | |
stack.push(n); | |
if(n.node.left != null && n.isLeftVisited == false){ | |
n.isLeftVisited = true; | |
n = new NodeInfo(n.node.left); | |
}// else if right side exists and is unvisited, go visit | |
else if(n.node.right != null && n.isRightVisited == false){ | |
n.isRightVisited = true; | |
n = new NodeInfo(n.node.right); | |
} | |
} | |
// if n.node is a leaf, add it to the result | |
result.add(n.node.val); | |
} | |
private boolean isLeafNode(NodeInfo n){ | |
if(n.node.left == null && n.node.right == null) return true; | |
return false; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment