二叉树-前,中,后序遍历(JAVA代码实现-迭代

前序遍历:先访问根节点,再递归遍历左子树,再递归遍历右子树

//根->左->右
public List<Integer> postorderTraversal(TreeNode root){
//定义一个列表用来接收遍历结果
 	List<Integer> res=new ArrayList<Integer>();
 	if(root==null){
	  return res;
	}
//定义一个栈用来辅助遍历
 Deque<TreeNode> stack=new LinkedList<TreeNode>();
//定义一个指针 指向根节点
	TreeNode node=root;
//循环条件 栈不为空或当前节点不为空
 while(!stack.isEmpty()||node!=null){
 	while(node!=null){
		res.add(node.val);//将根节点添加到res中
	  	  	stack.push(node);
	  	node=node.left;//开始遍历左子树
	}
   //当前节点为空时,从栈中弹出一个节点
   		node=stack.pop();
   //移动到栈顶节点的右子节点
   		node=node.right;
 }
 	return res;
}

中序遍历:先递归左子树,再访问根结点,再递归右子树

//左->根->右
public List<Integer> preorderTraversal(TreeNode root){
	List<Integer> res=new ArrayList<Integer>();
	if(root==null){
	  return res;
	}
  Deque<TreeNode> stack=new LinkedList<TreeNode>();
  TreeNode node=root;
  while(!stack.isEmpty()||node!==null){
	while(node!=null){
	stack.push(node);
	node=node.left;
	}
	node=stack.pop();
	res.add(node.val);
	node=node.right;
	}
  return res;
}

后序遍历:先递归左子树,再递归右子树,最后根节点

//左->右->根
public List<Integer> postorderTraversal(TreeNode root){
	List<Integer> res=new ArrayList<>();
  	if(root==null){
	  return res;
	}
  Deque<TreeNode> stack=new LinkedList<>();
  TreeNode prev=null;//用于记录上一个被访问的节点
  while(root!=null||!stack.isEmpty()){
	while(root!=null){
	  stack.push(root);
	  root=root.left;
	}
	TreeNode peekNode=stack.peek();//获取栈顶元素但不弹出
	//如果当前节点的右子树为空或者已经访问过,则可以访问当前节点
	if(peekNode.right==null||peekNode.right==prev){
	  stack.pop();//弹出当前节点
	  res.add(peekNode.val);//
	  prev=peekNode;//更新prev
	}else{
	  //否则,继续遍历右子树
	  	root=peekNode.right;
	}

有种简单的实现方式-递归

public List<Integer> inorderTraversal(TreeNode root){
  List<Integer>res = new ArrayList<Integer>();
  inorder(root,res);
  return res;
}
public void inorder(TreeNode root,List<Integer> res){
  if(root==null){
	return
	}
  inorder(root.left,res);
  res.add(root.val);
  inorder(root.right,res)
  }