先序:(每个节点左下延伸,沿途依次访问,且沿途依次将右孩子入栈。不能左下时,让出栈节点执行前面的过程)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<Integer> ans=new LinkedList<>();
LinkedList<TreeNode> sta=new LinkedList<>();
TreeNode p=root;
while(p!=null||!sta.isEmpty()){
while(p!=null){
ans.add(p.val);//访问
sta.add(p.right);//右孩子入栈
p=p.left;//往左下延伸
}
p=sta.removeLast();//让栈顶也做一次上面的循环
}
return ans;
}
}
中序:(每个节点沿左下延伸,沿途节点不访问并入栈。出栈一个访问一个,出栈的右孩子执行前面的过程)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<Integer> ans=new LinkedList<>();
LinkedList<TreeNode> sta=new LinkedList<>();
TreeNode p=root;
while(p!=null||!sta.isEmpty()){
while(p!=null){
sta.add(p);//左下延伸,沿途的节点不访问,入栈
p=p.left;
}
TreeNode node=sta.removeLast();
ans.add(node.val);
p=node.right;
}
return ans;
}
}
后序(链表的插入和先序不一样,且入栈的顺序相反):
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans=new LinkedList<>();
LinkedList<TreeNode> sta=new LinkedList<>();
TreeNode p=root;
while(p!=null||!sta.isEmpty()){
while(p!=null){
ans.addFirst(p.val);
sta.add(p.left);
p=p.right;
}
p=sta.removeLast();
}
return ans;
}
}