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