0106. Construct Binary Tree from Inorder and Postorder Traversal ================================================================ 题目信息 -------- :题号: 0106. 从中序与后序遍历序列构造二叉树 :难度: Medium :主题: 二叉树、分治、遍历序列、哈希索引 :原题: `LeetCode 0106 `_ :重点: 后序末端确定根,中序确定左右规模,再用反向游标按“根、右、左”消费节点 题目重述 -------- 给定长度相同的整数数组 ``inorder`` 和 ``postorder``,它们分别是一棵二叉树的中序遍历与后序遍历结果, 需要重建并返回原树。 中序顺序是“左子树、根、右子树”,后序顺序是“左子树、右子树、根”。两个数组包含相同且互不重复的节点 值,并保证来自同一棵有效二叉树,所以根位置和最终树都能唯一确定。数组长度在 ``1..3000`` 范围内,节点值 在 ``-3000..3000`` 范围内。 自建示例 -------- * 左右子树都存在:``inorder = [2,4,6,8,10,12]``、``postorder = [2,6,4,10,12,8]``,返回树的 层序表示为 ``[8,4,12,2,6,10]``; * 完全右斜:``inorder = [3,4,5]``、``postorder = [5,4,3]``,返回 ``[3,null,4,null,5]``; * 完全左斜:``inorder = [3,4,5]``、``postorder = [3,4,5]``,返回 ``[5,4,null,3]``; * 单节点:``inorder = [7]``、``postorder = [7]``,返回只含节点 ``7`` 的树。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: TreeNode* buildWithSlices(const std::vector& inorder, const std::vector& postorder) { if (inorder.empty()) { return nullptr; } const int rootValue = postorder.back(); int split = 0; while (inorder[split] != rootValue) { ++split; } const std::vector leftInorder(inorder.begin(), inorder.begin() + split); const std::vector rightInorder(inorder.begin() + split + 1, inorder.end()); const std::vector leftPostorder(postorder.begin(), postorder.begin() + split); const std::vector rightPostorder(postorder.begin() + split, postorder.end() - 1); TreeNode* root = new TreeNode(rootValue); root->left = buildWithSlices(leftInorder, leftPostorder); root->right = buildWithSlices(rightInorder, rightPostorder); return root; } TreeNode* buildWithRanges(const std::vector& postorder, int postBegin, int postEnd, int inBegin, int inEnd, const std::unordered_map& inorderIndex) { if (postBegin == postEnd) { return nullptr; } const int rootValue = postorder[postEnd - 1]; const int split = inorderIndex.at(rootValue); const int leftSize = split - inBegin; TreeNode* root = new TreeNode(rootValue); root->left = buildWithRanges(postorder, postBegin, postBegin + leftSize, inBegin, split, inorderIndex); root->right = buildWithRanges(postorder, postBegin + leftSize, postEnd - 1, split + 1, inEnd, inorderIndex); return root; } TreeNode* buildWithReverseCursor(const std::vector& postorder, int& postorderCursor, int inBegin, int inEnd, const std::unordered_map& inorderIndex) { if (inBegin == inEnd) { return nullptr; } const int rootValue = postorder[postorderCursor--]; const int split = inorderIndex.at(rootValue); TreeNode* root = new TreeNode(rootValue); root->right = buildWithReverseCursor(postorder, postorderCursor, split + 1, inEnd, inorderIndex); root->left = buildWithReverseCursor(postorder, postorderCursor, inBegin, split, inorderIndex); return root; } public: TreeNode* buildTree(std::vector& inorder, std::vector& postorder) { std::unordered_map inorderIndex; inorderIndex.reserve(inorder.size()); for (int index = 0; index < static_cast(inorder.size()); ++index) { inorderIndex[inorder[index]] = index; } int postorderCursor = static_cast(postorder.size()) - 1; return buildWithReverseCursor(postorder, postorderCursor, 0, static_cast(inorder.size()), inorderIndex); } }; 题解 ---- 根与左右边界 ~~~~~~~~~~~~ 后序遍历会先完成左右子树,最后访问根,因此任意非空子树对应的后序片段末值一定是根。确定根值后,它在 中序片段中的位置又把节点集合分为左右两侧: .. code-block:: text inorder = [左子树节点 | rootValue | 右子树节点] postorder = [左子树节点 | 右子树节点 | rootValue] 节点值互不相同,使根在中序中只有一个位置。中序左侧节点数决定后序片段中左、右子树的分界;对两个更小 片段重复相同操作,最终能唯一恢复全部父子关系。 切片直觉法 ~~~~~~~~~~ ``buildWithSlices`` 直接取 ``postorder.back()`` 作为根,再扫描 ``inorder`` 找到 ``split``。当前切片中, 中序左侧有 ``split`` 个节点,所以后序开头的 ``split`` 个值属于左子树,根之前的余下值属于右子树。 分别复制四个子数组并递归,空数组返回空指针。 这种做法与定义一一对应,但会在每层重新寻找根并复制片段。完全斜树每次只去掉一个根,累计扫描和复制量为 ``n + (n - 1) + ... + 1``,最坏达到 ``O(n²)``。要优化的不是分治结构,而是同一数组区间被反复查找和 搬运的工作。 索引与半开区间 ~~~~~~~~~~~~~~ ``buildWithRanges`` 以半开区间 ``[postBegin, postEnd)``、``[inBegin, inEnd)`` 描述同一子树,数组本身 不再复制。预先建立 ``节点值 -> 中序下标`` 的 ``inorderIndex`` 后,根位置 ``split`` 也不必线性扫描。 令 ``leftSize = split - inBegin``,根位于后序下标 ``postEnd - 1``,孩子区间为: .. code-block:: text 左子树 postorder:[postBegin, postBegin + leftSize) 左子树 inorder :[inBegin, split) 右子树 postorder:[postBegin + leftSize, postEnd - 1) 右子树 inorder :[split + 1, inEnd) 空半开区间满足起点等于终点,直接返回 ``nullptr``。区间方法消除了切片与找根扫描,但每个状态仍维护四个 边界,并依靠左子树规模计算右后序区间。 反向游标 ~~~~~~~~ 从后序数组末端向前读取,顺序不再是“左、右、根”,而是“根、右、左”。因此读取当前根后,紧邻的下一个 未消费值属于右子树;只要先递归右侧中序区间,再递归左侧中序区间,全局 ``postorderCursor`` 就会自然 消费当前子树对应的连续后序片段。 ``buildWithReverseCursor`` 只保留中序半开区间。进入非空区间时读取游标值并递减,根据哈希索引划分左右, 然后严格按照右、左顺序构造。显式后序边界、``leftSize`` 以及两个后序孩子区间全部从状态中消失。 递归顺序不能按通常书写习惯改成先左后右。根读取后游标正指向右子树最后访问的节点;若先把它交给左侧 中序区间,就会用右侧节点充当左子树根,后续划分即使索引正确也无法补救。 游标走读 ~~~~~~~~ 对 ``inorder = [2,4,6,8,10,12]``、``postorder = [2,6,4,10,12,8]``,游标从下标 ``5`` 开始: .. list-table:: :header-rows: 1 * - 中序区间 - 游标读取 - 根位置 - 下一次非空递归 * - ``[0,6)`` - 8 - 3 - 右区间 ``[4,6)`` * - ``[4,6)`` - 12 - 5 - 右为空,再进入左 ``[4,5)`` * - ``[4,5)`` - 10 - 4 - 两侧为空 * - ``[0,3)`` - 4 - 1 - 右区间 ``[2,3)`` * - ``[2,3)`` - 6 - 2 - 两侧为空 * - ``[0,1)`` - 2 - 0 - 两侧为空 右子树完成后,游标从值 ``12`` 一路消费到值 ``10``,随后自然停在左子树根 ``4``。单元素区间创建叶节点, 它的两个空区间不会继续读取游标。 主解与复杂度 ~~~~~~~~~~~~ 公开入口采用反向游标方案,因为它让中序序列只负责结构边界、后序游标只负责根的出现次序。节点值唯一是 索引无歧义和树唯一重建的必要前提;若允许重复值,单个 ``value -> index`` 映射无法决定当前根位置。 切片法最坏时间与额外复制量为 ``O(n²)``。区间法和反向游标法各创建每个节点一次;哈希表平均查询为 ``O(1)`` 时,期望时间为 ``O(n)``,索引工作空间为 ``O(n)``,递归栈为 ``O(h)``。哈希极端冲突下的 严格最坏时间取决于容器实现;返回树的 ``n`` 个新节点不计入工作空间。