二叉树三种非递归遍历

1.二叉树前序非递归遍历实现，（采用栈）

• 思路：(用一个栈)
  1.首先用cur标记树的根(root),当cur非空的时候；
  2.就直接打印根，并且将cur(也就是root)入栈；
  3.接着遍历根的左子树，一直遍历到最左边；
  4.当循环出来后，最左边的节点就已经入栈了；
  5.然后将栈此时非空(这就是最外面循环的一个条件)，就弹出栈顶元素，并且用cur标记弹出元素的右节点；
  6.所以如果右节点非空的时候还要将右边节点打印并且入栈，所以最外面还要增加一个条件，让右节点也被打印，就是cur不为空；

// 二叉树前序非递归遍历实现，（采用栈）void preOrderTraversal1(Node root){if (root == null)return;Stack<Node> stack = new Stack<>();Node cur = root;while(cur != null || !stack.empty()){while(cur != null){System.out.print(cur.val);stack.push(cur);cur = cur.left;}Node top = stack.pop();cur = top.right;}}

2.中序非递归遍历

• 思路：
  1.跟前序一样的原理，只是是先找到最左边的节点，打印了左边节点，才是打印根，然后右边节点；

//中序非递归遍历void inOrderTraversal1(Node root){if (root == null)return;Stack<Node> stack = new Stack<>();Node cur = root;while(cur != null || !stack.empty()){while(cur != null){stack.push(cur);cur = cur.left;}Node top = stack.pop();System.out.print(top.val);cur = top.right;}}

3. 后序非递归遍历

• 思路：
  1.后序遍历同样是通过cur找到将节点一个一个入栈，一直到最后面一个左节点，然后出栈，将左边节点打印；
  2.然后要判断是否存在右边节点，如果右节点为空，直接将根打印；
  3.但是会存在错误，就是会，因此需要将打印的节点用prev标记下来，以防后面，出现后面反复打印一个节点的情况
  4.就如下图，如果你不标记已经打印过的节点，当已经打印过去’H’这个节点，但是当你本来需要打印‘E’，然后发现它的右边节点 (cur.right)还是非空，又会将’H’入栈，因此需要标记，当cur.right == prev,就直接打印根，不需要再下去打印右节点,这样就可以进入if语句打印根节点。
  

//后序非递归遍历void postOrderTraversal1(Node root){if (root == null)return;Stack<Node> stack = new Stack<>();Node cur = root;Node prev=null;while(cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.peek();if (cur.right == null || cur.right == prev) {stack.pop();System.out.print(cur.val);prev = cur;cur = null;} else {cur = cur.right;}}}