使用非递归的方式遍历二叉树

前序遍历

前序遍历相对比较简单，将先弹出父节点，然后放入右节点，再放入左节点即可

/**
 * 非递归先序遍历二叉树
 *
 * @param root 二叉树根节点
 */
static void preOrderTravelByStack(BinTreeNode root, Consumer<BinTreeNode> action) {
    var stack = new Stack<BinTreeNode>();
    if (root != null) {
        stack.push(root);
        while (!stack.isEmpty()) {
            var node = stack.pop();
            if (action != null) {
                action.accept(node);
            }
            if (node.getRight() != null) {
                stack.push(node.getRight());
            }
            if (node.getLeft() != null) {
                stack.push(node.getLeft());
            }
        }
    }
    System.out.println();
}

中序遍历

中序遍历的实现思路就是模仿递归的形式，先遍历最左边的节点，然后打印，然后弹出来遍历右边的节点，然后又不断遍历左边的节点

/**
 * 非递归中序遍历二叉树
 *
 * @param root 二叉树根节点
*/
static void inOrderTravelByStack(BinTreeNode root, Consumer<BinTreeNode> action) {
    var stack = new Stack<BinTreeNode>();
    var head = root;
    while (!stack.isEmpty() || head != null) {
        if (head != null) {
            stack.push(head);
            head = head.getLeft();
        } else {
            head = stack.pop();
            action.accept(head);
            head = head.getRight();
        }
    }
}

后续遍历

后续遍历相对比较复杂，这里采用两个栈 s1, s2 来实现

1. 将 head 压入 s1
2. 从 s1 弹出节点 cur, 将 cur 的 left 和 right 压入 s1, 将 cur 压入 s2
3. 不断重复上面的过程，直到 cur 为空
4. 从 s2 弹出的顺序就是后续遍历的顺序

 /**
  * 非递归后续遍历二叉树
  *
  * @param root   二叉树的根节点
  * @param action 遍历算法的指针
  */
static void postOrderTravelByStack(BinTreeNode root, Consumer<BinTreeNode> action) {
    var stack1 = new Stack<BinTreeNode>();
    var stack2 = new Stack<BinTreeNode>();
    var head = root;
    stack1.push(head);
    while (!stack1.isEmpty()) {
        head = stack1.pop();
        if (head.getLeft() != null) {
            stack1.push(head.getLeft());
        }
        if (head.getRight() != null) {
            stack1.push(head.getRight());
        }
        stack2.push(head);
    }

    while (!stack2.isEmpty()) {
        action.accept(stack2.pop());
    }
}