非递归后序遍历二叉树

### 非递归后序遍历二叉树的实现

对于非递归方式实现二叉树的后序遍历，可以采用栈结构来模拟递归调用过程。具体做法如下：

在该方法中，使用一个栈保存节点，并按照根节点先于子节点访问的原则压入栈内。为了适应后序遍历的要求——即左子树->右子树->根节点这一顺序，在每次弹出元素时将其值插入到列表头部位置，从而实现了反向存储的结果集。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            root = stack.pop();
            list.add(0, root.val); // 将当前结点值添加至链表首部
            
            if (root.left != null) {
                stack.push(root.left);
            }
            
            if (root.right != null) {
                stack.push(root.right);
            }
        }

        return list;
    }
}

上述代码展示了如何利用Java中的`Stack`类以及`LinkedList`作为返回容器完成整个操作流程[^3]。

另外一种思路是通过两次反转的方法来进行处理：第一次正常前序遍历时改变左右孩子的入栈次序；第二次再整体翻转最终得到的数据序列即可获得正确的后序遍历结果。

Python版本同样适用此逻辑：

def postorderTraversal(self, root: TreeNode) -> List[int]:
    result = []
    if not root:
        return []

    stack = [root]

    while stack:
        node = stack.pop()
        result.insert(0, node.val)

        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result

这两种方案都能有效地解决非递归形式下的二叉树后序遍历问题[^4]。