二叉树的前序遍历
虽然我们说的是不用递归的方式实现，但是我们的思路还是模拟递归的实现，那么我们如何不用递归来模拟实现递归呢？我们要想模拟递归，我们需要知道实现递归的底层逻辑是什么？递归实际上是通过栈这个数据结构来实现的，我们都知道递归的顺序是先完成后递归的，这也就跟栈先进后出的原理是类似的，所以我们想模拟递归，也需要借用栈这个数据结构。
在知道了原理之后，我们接下来就需要知道怎么样来实现了，因为这里是前序遍历，先遍历根节点，然后是左子树，最后是右子树，所以我们先遍历左子树，并且在遍历的同时我们将遍历的节点存储在栈中并打印，方便我们找到节点的右子树。当我们的root遍历到为null时，就说明左树遍历完了，我们就将栈顶的节点弹出，将root等于弹出节点的右子树，直到root等于null并且栈为空时完成遍历。
节点6的右树也为null，所以我们弹出栈顶的元素，cur = top.right，继续上面操作。
public void preOrderNor(TreeNode root) { if(root == null) { return; } TreeNode cur = root; Deque<TreeNode> stack = new ArrayDeque<>(); while(cur != null || !stack.isEmpty()) { while(cur != null) { stack.push(cur); System.out.println(cur.val); cur = cur.left; } TreeNode top = stack.pop(); cur = top.right; } }
二叉树的中序遍历
中序遍历的思路跟前序遍历的思路是一样的，只是打印的顺序不同，我们在从栈中弹出节点的同时打印。
public void inOrderNor(TreeNode root) { if(root == null) { return; } Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while(cur != null || !stack.isEmpty()) { while(cur != null) { stack.push(cur); cur = cur.left; } TreeNode top = stack.pop(); System.out.println(top.val); cur = top.right; } }
二叉树的后序遍历
后序遍历的思路跟前序和中序的思路是不同的，我们需要判断什么时候该打印，因为是后序遍历，所以我们需要在遍历完右树或者右树为null的时候在遍历根节点。
public void postOrderNor(TreeNode root) { if(root == null) { return; } TreeNode cur = root; TreeNode prev = null; Deque<TreeNode> stack = new ArrayDeque<>(); while(cur != null || !stack.isEmpty()) { while(cur != null) { stack.push(cur); cur = cur.left; } TreeNode top = stack.peek(); if(top.right == null || top.right == prev) { System.out.println(top.val); stack.pop(); prev = top; }else { cur = top.right; } } }
