如何实现二叉树的后序遍历非递归算法？

二叉树的后序遍历(Postorder Traversal)问题是先后序遍历左子树,然后后序遍历右子树,最后访问根节点。

我们可以使用栈实现二叉树的后序遍历非递归算法:

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

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    TreeNode prev = null;

    while (!stack.isEmpty()) {
        TreeNode curr = stack.peek();
        if (prev == null || prev.left == curr || prev.right == curr) {
            if (curr.left != null) stack.push(curr.left);
            else if (curr.right != null) stack.push(curr.right);
        } else if (curr.left == prev) {
            if (curr.right != null) stack.push(curr.right);
        } else {
            stack.pop();
            result.add(curr.val);
        }
        prev = curr;
    }

    return result;
}

算法流程:

1. 定义result存储结果,stack用于后序遍历,prev记录上一个访问的节点。
2. 根节点入栈。
3. 当栈非空循环:

• curr为栈顶节点,prev为空或prev是curr的左右子节点,curr的左右子节点入栈。
• curr的左子节点为prev,右子节点入栈。
• 否则出栈curr访问,prev指向curr。

1. 重复步骤3,直到栈为空,返回result。
2. 特殊情况,root为空,返回result。

时间复杂度O(n),空间复杂度O(n)。

所以,二叉树后序遍历的关键是:

1. 使用栈模拟递归调用栈,prev记录上一个访问的节点。
2. 根据prev的位置判断如何处理curr节点:左右子节点入栈;右子节点入栈;出栈curr访问。
3. 重复步骤2,直到栈为空,得到结果。
4. 与递归后序遍历相比,只是使用栈和prev代替了递归调用栈。