递归遍历只要修改递归的顺序即可
记录一下二叉树前中后遍历的迭代法
/**
*统一一下
*@paramroot
*@return
*/
//前序
public static ListpreOrder(TreeNode root){
List<Integer>list = newArrayList();
Stack stack =newStack();
TreeNode cur = root;
while(cur!=null||!stack.isEmpty()){
//一直往左压入栈
while(cur!=null){
list.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return list;
}
//中序
public ListinorderTraversal(TreeNode root) {
if(root == null){
return newArrayList();
}
List<Integer>list = newArrayList();
Stack stack =newStack();
TreeNode cur = root;
while(cur != null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
//后序遍历，非递归
public static ListpostOrder(TreeNode root){
Stack stack =newStack<>();
List<Integer>list = newArrayList<>();
TreeNode cur = root;
TreeNode p =null;//用来记录上一节点
while(!stack.isEmpty()|| cur != null){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
// 后序遍历的过程中在遍历完左子树跟右子树cur都会回到根结点。所以当前不管是从左子树还是右子树回到根结点都不应该再操作了，应该退回上层。
// 如果是从右边再返回根结点，应该回到上层。
//主要就是判断出来的是不是右子树，是的话就可以把根节点=加入到list了
if(cur.right== null||cur.right == p){
list.add(cur.val);
stack.pop();
p = cur;
cur =null;
}else{
cur = cur.right;
}
}
return list;
}
网友评论