前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(!stack.isEmpty()||p!=null){
if(p!=null){
stack.push(p);
list.add(p.val); // Add before going to children
p=p.left;
}else{
TreeNode node=stack.pop();
p=node.right;
}
}
return list;
}
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(!stack.isEmpty()||p!=null){
if(p!=null){
stack.push(p);
p=p.left;
}else{
TreeNode node=stack.pop();
list.add(node.val);// Add after all left children
p=node.right;
}
}
return list;
}
后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<Integer>();
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;
while(!stack.isEmpty()||p!=null){
if(p!=null){
stack.push(p);
list.addFirst(p.val);// Reverse the process of preorder
p=p.right;
}else{
TreeNode node=stack.pop();
p=node.left;
}
}
return list;
}