0145. Binary Tree Postorder Traversal¶
题目信息¶
- 题号:
二叉树的后序遍历
- 难度:
Easy
- 主题:
二叉树、深度优先搜索、访问阶段、序列反转
- 原题:
- 重点:
识别根节点必须等待两个子树完成的状态,再用根右左序列的整体反转消除显式阶段标记
题目重述¶
给定二叉树根节点 root,返回后序遍历结果。对每棵非空子树,先完整遍历左子树,再完整遍历右子树,
最后访问根节点。每个结构节点都要输出一次;空树返回空数组。
自建示例¶
root = [6, 2, 9, null, 4, 7, null]:结果为[4, 2, 7, 9, 6];单节点树
[5]:左右子树都为空,最后输出根,得到[5];只有左链
3 -> 2 -> 1:最深节点先返回,结果为[1, 2, 3]。
C++ 实现¶
#include <algorithm>
#include <stack>
#include <utility>
#include <vector>
class Solution {
private:
void recursivePostorder(
TreeNode* node,
std::vector<int>& result
) {
if (node == nullptr) {
return;
}
recursivePostorder(node->left, result);
recursivePostorder(node->right, result);
result.push_back(node->val);
}
std::vector<int> postorderWithExpandedFlag(TreeNode* root) {
std::vector<int> result;
std::stack<std::pair<TreeNode*, bool>> pending;
if (root != nullptr) {
pending.push({root, false});
}
while (!pending.empty()) {
auto [node, childrenExpanded] = pending.top();
pending.pop();
if (childrenExpanded) {
result.push_back(node->val);
continue;
}
pending.push({node, true});
if (node->right != nullptr) {
pending.push({node->right, false});
}
if (node->left != nullptr) {
pending.push({node->left, false});
}
}
return result;
}
std::vector<int> reverseRootRightLeft(TreeNode* root) {
std::vector<int> result;
if (root == nullptr) {
return result;
}
std::stack<TreeNode*> pending;
pending.push(root);
while (!pending.empty()) {
TreeNode* node = pending.top();
pending.pop();
result.push_back(node->val);
if (node->left != nullptr) {
pending.push(node->left);
}
if (node->right != nullptr) {
pending.push(node->right);
}
}
std::reverse(result.begin(), result.end());
return result;
}
public:
std::vector<int> postorderTraversal(TreeNode* root) {
return reverseRootRightLeft(root);
}
};
题解¶
后序与前序的关键差异是输出时机¶
前序第一次遇到节点就能输出;后序必须等左、右子树都完成后才输出根。recursivePostorder 的函数调用栈
不仅保存节点,还隐含当前执行到哪个阶段:左调用返回后还要进右子树,右调用返回后才记录根值。
若迭代时只把节点地址放栈并在弹出时立刻输出,会得到某种根优先顺序,不可能直接满足左右根。显式实现 首先要回答:同一个节点这次出栈,是准备展开孩子,还是孩子已经处理完、可以输出?
方案一:为栈帧增加访问阶段¶
postorderWithExpandedFlag 的栈元素为 (node, childrenExpanded)。首次弹出 false 状态时不输出,
而是按以下顺序压栈:
(node, true)
(node.right, false)
(node.left, false)
由于后进先出,左子树先处理,右子树随后处理,最后才重新弹出 (node, true) 并输出根。这正是递归帧
“调用孩子前”与“两个调用都返回后”的显式表示。每个节点入栈两次,但每个阶段只做常数工作。
具体走读根节点的等待状态¶
对根 6 及左右孩子 2、9,栈顶写在右侧:
弹出状态 |
动作 |
根何时输出 |
|---|---|---|
|
压 |
暂不输出 |
|
完成其左、右子树后输出 |
根仍在栈底等待 |
|
完成其左、右子树后输出 |
根仍未输出 |
|
两侧已完成 |
此时输出 |
这套状态与递归最接近,也能扩展到需要进入/退出事件的树算法。
结构变换:后序是根右左的反序¶
目标后序为 左子树 + 右子树 + 根。将整个序列反转会得到
根 + reverse(右子树后序) + reverse(左子树后序);递归地看,这恰好是先根、再右子树、最后左子树的
遍历。因此可以先生成 根、右、左 序列,再原地整体反转,不再为每个节点保存访问阶段。
要让栈弹出顺序是根、右、左,弹出根后必须先压左孩子、再压右孩子;右孩子后入先出。这个压栈顺序与普通 前序的根、左、右正好相反。
为什么必须整体反转而不是只交换孩子¶
只把前序中的左右顺序交换,会得到根右左,根仍在子树之前。整体反转同时把根移动到最后,并把每棵子树块 内部的根右左递归转换为左右根。它不是层序反转,也不是只反转每层;后序要求完整左子树块位于完整右子树块 之前,只有深度优先序列的整体反转保持这种嵌套关系。
以示例为例,栈先生成:
根右左:6, 9, 7, 2, 4
整体反转:4, 2, 7, 9, 6
反转后的每个子树都满足左、右、根。
正确性与主解选择¶
阶段标记法严格模拟递归返回顺序,所以每个节点在两侧完成后输出一次。反序法生成的根右左序列与后序在 整棵树及每个递归子树上互为反序,因此整体反转后同样不重不漏。空树在压栈前直接返回空结果。
公开入口采用根右左加反转:每个节点只压栈一次,代码状态较少;代价是在最终结果上多做一次 O(n)
原地反转。阶段标记法不需要反转,却让每个节点以两种状态入栈,适合不能延迟输出的场景。两者时间均为
O(n)、工作栈最坏 O(h) 至 O(n);返回数组 O(n) 不计入工作空间。递归版使用 O(h)
调用栈,作为遍历定义的直接起点保留。