日野弥生：勉強しよう
LeetCode 145 - 二叉树的后序遍历
发表于2025年02月15日
递归法可以无脑解决先序、中序、后序遍历。
class Solution {
private:
vector<int> m_result{};
public:
void postorderTraversalImpl(TreeNode* root)
{
if(!root)
return;
postorderTraversalImpl(root->left);
postorderTraversalImpl(root->right);
m_result.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
postorderTraversalImpl(root);
return m_result;
}
};非递归法也是利用栈结构模拟函数栈进行深度优先搜索。注意，此处和前序遍历的迭代版本不同的是，我们需要进栈的数据需要有一个标记值，标记当前结点是否需要处理右子树。
以下代码和中序遍历的非迭代版本的差异只在于当前结点和右子树的进栈顺序有差异。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = deque()
result = []
while root is not None or stack:
if root is not None:
# 根节点进栈，由于当前根节点的右子树已经在上面一行代码中进过栈，所以标记值为True
stack.append([root, True])
# 中序遍历最后处理右子树，所以右子树先进栈，标记值False也一同进栈，表达该右子树作为结点并没有遍历过
if root.right is not None:
stack.append([root.right, False])
root = root.left
else:
# 左子树到底时出栈
item = stack.pop()
# 注意此处的key和value的获取方式
key = item[0]
value = item[1]
if value == False:
# 如果该节点没被标记，说明该节点应该被正常地进行迭代，即需要把当前结点和该节点的右子树进栈并继续遍历左子树
root = key
else:
# 如果已经被标记，说明右子树被遍历，此时只需直接记录结构并置空即可
result.append(key.val)
root = None
return result