java非递归实现之二叉树的前中后序遍历详解

 //非递归 //根 左 右 class Solution { public List preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List list = new ArrayList<>(); if(root==null)  return list; //创建一个栈 Stack st = new Stack<>(); //cur指向根节点 TreeNode cur = root; while(!st.isEmpty()||cur!=null){ //一边向左遍历，一边将遍历到的节点入栈，节点值入数组 while(cur!=null){ list.add(cur.val); st.push(cur);	//根 cur=cur.left;	//左 } //指针指向栈顶节点（即上一个节点），并将栈顶节点出栈 cur = st.pop(); //指针指向该节点的右子树，开始下一轮的遍历 cur = cur.right;	//右 } return list; } } 

 //非递归 //左 根 右 class Solution { public List inorderTraversal(TreeNode root) { List list = new ArrayList<>(); if(root==null)    return list; Stack st = new Stack<>(); TreeNode cur = root; while(!st.isEmpty()||cur!=null){ //一边向左遍历，一边将遍历到的节点入栈 while(cur!=null){ st.push(cur); cur = cur.left;	//左 } cur = st.pop(); //存储遍历结果 list.add(cur.val);	//根 cur = cur.right;		//右 } return list; } } 

 //非递归 //左 右 根 class Solution { public List postorderTraversal(TreeNode root) { List list = new ArrayList<>(); if(root==null) return list; TreeNode cur = root; //关键在于定义一个cur的前驱节点 TreeNode pre = null; Stack st = new Stack<>(); while(cur!=null||!st.isEmpty()){ //一边向左遍历，一边将遍历到的节点入栈 while(cur!=null){ st.push(cur); cur = cur.left; } cur = st.pop(); //若该节点的右节点为空，或者右节点被遍历过，数组才能存储该节点的数值（也就是我们最后才遍历的根） if(cur.right==null||cur.right==pre){ list.add(cur.val); pre = cur; cur=null; }else{//如果不满足，说明该节点的右节点还没有被遍历过，那么接着向右子节点遍历 st.push(cur); cur=cur.right; } } return list; } }