递归的函数调用就是通过栈来实现的，因此二叉树的非递归实现也可借助栈来完成
先序遍历
要按照根-左-右的顺序遍历，我们先将头结点压入栈中，只要栈不为空，就弹出一个结点并打印，然后依次压入该弹出结点的右结点和左结点。
public static void preOrder(TreeNode head) {
if (head != null) {
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.val + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
System.out.println();
}
}
中序遍历
要按照左-根-右的顺序遍历，
1）先将子树根及其左边界入栈
2）弹出栈顶结点并打印，然后对该结点的右子树重复1）
3）没子树且栈空，结束
public static void inOrder(TreeNode head) {
if (head != null) {
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.val + " ");
head = head.right;
}
}
System.out.println();
}
}
可见，只有处理完左子树和自身之后，才处理右子树，也就实现了中序遍历。
后续遍历
两个栈实现
先序遍历是按照根-左-右的顺序去实现的，我们可以修改先序遍历的方法，使其按照根-右-左来打印结点，而我们可以不打印结点，改为将其入栈，遍历完之后出栈，就可以得到左-右-根的打印顺序，也即后序遍历。
public static void posOrderTwoStacks(TreeNode head) {
if (head != null) {
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> collect = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
head = stack.pop();
collect.push(head);
if (head.left != null) {
stack.push(head.left);
}
if (head.right != null) {
stack.push(head.right);
}
}
while (!collect.isEmpty()) {
System.out.print(collect.pop().val + " ");
}
System.out.println();
}
}
一个栈实现
首先定义一个哨兵h，初始时h指向二叉树的根结点，将h入栈。之后h指向上一次处理过的结点，弹出处理栈顶元素，
1）有左树且左树没有处理过（即h不指向左树），左树入栈；
2）有右树且右树没有处理过（即h不指向右树），右树入栈；
3）左右树为空或左右树都处理过了，打印该结点，并将h指向该结点
public static void posOrderOneStack(TreeNode h) {
if (h != null) {
Stack<TreeNode> stack = new Stack<>();
stack.push(h);
// 如果始终没有打印过节点，h就一直是头节点
// 一旦打印过节点，h就变成打印节点
// 之后h的含义 : 上一次打印的节点
while (!stack.isEmpty()) {
TreeNode cur = stack.peek();
if (cur.left != null && h != cur.left && h != cur.right) {
// 有左树且左树没处理过
stack.push(cur.left);
} else if (cur.right != null && h != cur.right) {
// 有右树且右树没处理过
stack.push(cur.right);
} else {
// 左树、右树 没有 或者 都处理过了
System.out.print(cur.val + " ");
h = stack.pop();
}
}
System.out.println();
}
}
时间、空间复杂度分析
对于一个栈实现的先中后序遍历，由于每个结点都要入栈和出栈一次，故时间复杂度为O（n），空间复杂度为O（h），h为二叉树的树高，也就是栈的最大深度。
而两个栈实现的后序遍历，时间复杂度为O（n），由于需要收集所有结点，再从栈里弹出，因此空间复杂度为O（n）。
