二叉树的非递归后序遍历算法实例详解

二叉树的后序遍历是先遍历左子树，再遍历右子树，最后遍历根节点的顺序。使用递归方式实现比较简单，但是非递归方式实现却有一定难度。

本文将详细讲解如何使用非递归方式实现二叉树的后序遍历，并提供相应的示例说明。

算法思路

可以使用两个栈来实现二叉树的后序遍历。

首先将根节点压入栈A中，然后从栈A中弹出一个节点，将该节点压入栈B中，接着将该节点的左子树和右子树分别压入栈A中。

从栈A中弹出的节点必定是左子树或右子树节点，这时需要判断该节点是否已经在栈B中，如果不在则将该节点压入栈B中，否则说明该节点的左子树和右子树已经遍历完成，将该节点从栈A中弹出并压入栈B中。

重复以上操作直到栈A为空，最终栈B中的元素顺序即为二叉树的后序遍历结果。

代码实现

下面是Java语言实现的二叉树的非递归后序遍历算法：

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Stack<TreeNode> stackA = new Stack<>();
    Stack<TreeNode> stackB = new Stack<>();
    stackA.push(root);

    while (!stackA.isEmpty()) {
        TreeNode node = stackA.pop();
        stackB.push(node);
        if (node.left != null) {
            stackA.push(node.left);
        }
        if (node.right != null) {
            stackA.push(node.right);
        }
    }

    while (!stackB.isEmpty()) {
        result.add(stackB.pop().val);
    }

    return result;
}

示例说明

假设我们有如下二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

使用上述代码实现后序遍历的结果应该为：{4, 5, 2, 6, 7, 3, 1}。

假设我们有如下二叉树：

    1
     \
      2
     /
    3

使用上述代码实现后序遍历的结果应该为：{3, 2, 1}。

以上就是二叉树的非递归后序遍历算法实例的详细讲解，如果有疑问欢迎提出。