#题目: 用非递归的方式写一下二叉树的遍历 分别包含前序遍历 中序遍历 和 后序遍历 谢谢阿毛同学,他对这三个遍历理解比较深刻
#method 1 先写 前序遍历 理解起来较容易
//这个非递归版本的前序遍历很容易理解 public void preOrderTravelse(TreeNode root){ if(root == null){ return; } Stack<TreeNode> sta = new Stack<>(); sta.push(root); while(sta.size()>0){ TreeNode cur = sta.peek(); sta.pop(); System.out.print(cur.val+" "); if(cur.right != null){ sta.push(cur.right); } if(cur.left != null){ sta.push(cur.left); } } }
#method 2 中序遍历 结合注释看看,理解起来很轻松
//这个非递归版本的中序遍历也需要好好理解 public void inOrderTravelse(TreeNode root){ if(root == null){ return; } Stack<TreeNode> sta = new Stack<>(); TreeNode p = root; while(p !=null || sta.size()>0){ //p是指我们要压入栈中的节点 只看左子树 while(p!=null){ sta.push(p); p = p.left; } //这个结束后 p = null if(sta.size()>0){ //cur是指我们要弹出栈的节点 只看右子树 TreeNode cur = sta.pop(); System.out.print(cur.val+" "); if(cur.right != null){ p = cur.right; } } } }
#method 3 最后这个非递归的后序遍历版本是我见过最容易理解的。。。。。。
//这个非递归版本的后序遍历简直不要太简单 public void postOrderTravelse(TreeNode root){ if(root == null){ return; } Stack<TreeNode> sta = new Stack<>(); sta.push(root); while(sta.size()>0){ TreeNode cur = sta.peek(); if(cur.left==null && cur.right==null){ System.out.print(cur.val+" "); sta.pop(); } if(cur.right !=null){ sta.push(cur.right); cur.right = null; } if(cur.left != null){ sta.push(cur.left); cur.left = null; } } }