Coding：二叉树的非递归后序遍历怎么写？（给出思路与代码）

Coding: How do you implement iterative postorder traversal of a binary tree?

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Coding, Data Structures

标签: binary tree, postorder, iterative, stack

参考答案摘要

答案 后序遍历是 left→right→root。非递归常见两种写法： 双栈法 ：第一个栈做类似前序（root→left→right），把弹出的节点压入第二个栈，最后第二个栈逆序输出即后序。 单栈 + prev 指针 ：沿左链入栈；看栈顶节点，如果它有右子树且右子树没处理过，就转向右子树；否则弹栈输出，并把 prev 置为该节点。 Python 示例（单栈） def postorder_trave...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。