面试题7：重建二叉树

以前序首项确定根，在中序中切分左右区间，递归重建唯一值二叉树并验证非法遍历序列。

学习目标

  • 能以前序首项确定根，在中序中切分左右区间递归重建二叉树
  • 能解释"唯一值"是重建的关键前提
  • 能验证非法遍历序列并拒绝

从两份遍历为何能还原开始

先预测：只给前序[1,2,3]，2是1的左孩子还是右孩子？两种树都可能产生同一前序。只给中序也同样无法确定根。把前序和中序结合，前序首项告诉我们根是谁，中序中根的左右两侧告诉我们哪些节点属于左右子树。

这道“”给出某棵二叉树的前序遍历和中序遍历，节点值不重复，要求构造原树并返回根节点。官方样例：

preorder = [1, 2, 4, 7, 3, 5, 6, 8]
inorder  = [4, 7, 2, 1, 5, 3, 8, 6]

的第一个节点是当前子树根；把当前根左侧划为左子树、右侧划为右子树。算法据此递归划分左右子树。

前序给根，中序给左右边界前序12473568中序47215386根1把中序分为3个左节点和4个右节点左子树pre=[2,4,7] · in=[4,7,2]右子树pre=[3,5,6,8] · in=[5,3,8,6]对子区间重复同一规则，直到区间为空或只剩一个节点。
左子树大小来自中序根位置，并决定前序序列切分点。

一层递归要确定

在当前前序区间[preStart, preEnd]中，preorder[preStart]是根值。找到它在当前中序区间的位置rootInorder后，左子树节点数为leftSize = rootInorder - inStart。

于是左子树前序区间是根后面的leftSize个元素，中序区间是根左侧；右子树前序区间是剩余元素，中序区间是根右侧：

left preorder : [preStart + 1, preStart + leftSize]
left inorder  : [inStart, rootInorder - 1]
right preorder: [preStart + leftSize + 1, preEnd]
right inorder : [rootInorder + 1, inEnd]

是两种序列之间的桥梁。不能凭前序值大小切分，也不能假定二叉搜索树；原树只是一般二叉树，节点数值没有排序语义。

检查前序中序要求
区间长度preEnd-preStartinEnd-inStart必须相等
当前根preorder[preStart]应位于当前中序区间缺失即非法
左子树根后leftSize项根左侧leftSize项长度一致
右子树剩余前序项根右侧项长度一致
递归不是只找根：每一层都要验证两种遍历描述的是同一批节点。

必须在每层保持。若根值不在当前中序区间，即使它出现在中序数组其他位置，也说明两份遍历在当前子树结构上矛盾，应报告非法输入。

忠实理解作者的指针区间实现

作者源码用四个指针表示两个闭区间。它取startPreorder[0]为根，在线性扫描中序区间定位根，再按leftLength递归：

int rootValue = startPreorder[0];
int* rootInorder = startInorder;
while (rootInorder <= endInorder &&
       *rootInorder != rootValue) {
    ++rootInorder;
}
if (rootInorder > endInorder) {
    throw InvalidInput{};
}
 
const int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPreorder + leftLength;
 
root->left = leftLength > 0
    ? construct(startPreorder + 1, leftPreorderEnd,
                startInorder, rootInorder - 1)
    : nullptr;
root->right = leftLength < endPreorder - startPreorder
    ? construct(leftPreorderEnd + 1, endPreorder,
                rootInorder + 1, endInorder)
    : nullptr;

单节点是重要基线：前序和中序都只剩一个元素时，两值必须相同才能创建叶节点，否则输入冲突。空输入在入口返回空树，不进入核心递归。

官方每层扫描当前中序区间。平衡树各层扫描总量约为O(n log n)量级，退化树可能扫描n + (n-1) + ...，最坏O(n²)。这不影响原理，但可以预处理中序值到下标的映射，把每次定位降到平均O(1)。

索引表优化与异常安全所有权

节点值不重复时，可以为中序遍历建立value → index映射。下面用半开中序区间[begin,end)和单调前序游标，减少四个闭区间边界的加减：

#include <memory>
#include <span>
#include <stdexcept>
#include <unordered_map>
 
struct TreeNode {
    int value;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
};
 
class TreeBuilder {
public:
    std::unique_ptr<TreeNode> build(
        std::span<const int> preorder,
        std::span<const int> inorder
    ) {
        if (preorder.size() != inorder.size()) {
            throw std::invalid_argument("length mismatch");
        }
        preorder_ = preorder;
        index_.clear();
        for (std::size_t i = 0; i < inorder.size(); ++i) {
            if (!index_.emplace(inorder[i], i).second) {
                throw std::invalid_argument("duplicate value");
            }
        }
 
        next_preorder_ = 0;
        auto root = build_range(0, inorder.size());
        if (next_preorder_ != preorder.size()) {
            throw std::invalid_argument("unmatched traversal");
        }
        return root;
    }
 
private:
    std::unique_ptr<TreeNode> build_range(
        std::size_t in_begin,
        std::size_t in_end
    ) {
        if (in_begin == in_end) return nullptr;
        if (next_preorder_ >= preorder_.size()) {
            throw std::invalid_argument("preorder exhausted");
        }
 
        const int root_value = preorder_[next_preorder_++];
        const auto found = index_.find(root_value);
        if (found == index_.end() ||
            found->second < in_begin ||
            found->second >= in_end) {
            throw std::invalid_argument("root outside inorder range");
        }
 
        auto root = std::make_unique<TreeNode>();
        root->value = root_value;
        root->left = build_range(in_begin, found->second);
        root->right = build_range(found->second + 1, in_end);
        return root;
    }
 
    std::span<const int> preorder_;
    std::unordered_map<int, std::size_t> index_;
    std::size_t next_preorder_ = 0;
};

std::unique_ptr保证后续子树构造抛异常时，已经创建的部分树会自动释放。若使用裸new并在深层发现非法输入，必须显式销毁之前创建的节点，否则错误路径泄漏内存。

索引表版本平均时间O(n)，因为每个节点创建一次、映射查询平均常数；额外空间O(n)用于映射和节点，递归栈深度O(h)，其中h是树高。最坏退化树h=n，仍可能耗尽调用栈。

为何是关键前提

依赖节点值可唯一定位。中序有两个相同值时，前序根值对应哪个位置不确定，不同切分可能产生不同树；简单unordered_map<int,index>还会覆盖前一个位置。

如果节点有唯一ID但展示值可重复，应使用ID重建；如果只有重复值，需要额外信息，例如空节点标记、节点身份或其他遍历约束。不能任意选择第一个匹配位置后仍宣称恢复了原树。

长度相等也不够。preorder=[1,2,3]与inorder=[3,1,4]长度相同，但元素集合不同；根2或后续根会找不到。即使集合相同，根若不在当前中序子区间，也代表递归结构冲突。

入口可先比较唯一元素集合，提前给出清晰错误；核心递归仍要验证当前区间，因为全局集合一致不能代替局部分割一致。错误应在返回半成品树之前传播，调用方才能区分空树与非法遍历。

深树、迭代方案与资源上界

全左树的前序为[1,2,3,4,5]、中序为[5,4,3,2,1]；全右树两序列同为[1,2,3,4,5]。它们让递归深度达到n，也是官方测试专门覆盖的两种形状。

数据规模可控时递归最清晰。若可能有数十万节点，应考虑显式任务栈或限制深度；仅把中序查找优化为哈希不能解决调用栈上限。迭代重建通常维护祖先栈和中序游标，证明更复杂，也要保留非法输入验证。

构造n个节点本身需要O(n)输出空间，这不算可避免的辅助空间。复杂度说明应区分结果树、索引表和递归栈；只写“空间O(n)”虽然数量级正确，却看不出资源来自哪里。

验证应重新生成两种遍历

遍历组合与唯一性边界

中序遍历之所以关键，是它把根两侧明确分成左子树和右子树。后序遍历的最后一项也能给出根，因此“中序 + 后序”同样可唯一重建唯一值二叉树，只是递归通常从后序末端取根，并先确定右子树区间。

“前序 + 后序”一般仍不够。对只有根1和孩子2的树，2作为左孩子或右孩子时，前序都是[1,2]，后序都是[2,1]。若额外保证每个内部节点恰有两个孩子，即满二叉树，才可借子树根与长度恢复；不能把这个附加条件偷带回一般二叉树。

层序加中序也能在唯一值前提下重建，但每层要从层序中筛出属于左右中序集合的节点，实现和复杂度不同。选择遍历组合时先问：哪一份序列提供根，哪一份提供左右分割；若两者都只提供根相对先后而不提供分割，通常存在歧义。

把构造当成一次事务

非法输入可能在递归很深处才被发现。函数不应把半棵树作为成功结果返回，也不应泄漏已经创建的节点。unique_ptr让局部根拥有左右子树，任何异常都会沿所有权链自动清理；只有整个递归成功后，根指针才提交给调用者。

不使用异常时，可以返回expected<unique_ptr<TreeNode>, BuildError>一类结果，把长度不匹配、重复值、缺失节点、根越界和深度超限分别编码。单纯返回nullptr会把合法空树与非法输入混在一起，调用方无法判断是否应该修复数据。

构造器对象若被重复使用，还要在每次调用前清空索引和前序游标。上一次失败留下的next_preorder_不能污染下一次构建；把状态限制在一次调用的局部上下文更容易保证线程安全和可重入。

深度预算与拒绝策略

树高不只影响栈空间，也影响后续树算法。来自外部的退化遍历可以让构造、销毁和再次验证都形成深递归，成为拒绝服务输入。接口可在递归参数中记录深度，超过配置上限就返回错误，或使用显式栈完成构建与销毁。

深度上限不能随意写死为“1000”。应根据线程栈预算、每帧大小、平台和业务允许树高确定，并通过最坏形状测试。即使改用显式栈避免调用栈溢出，输出树本身仍有n个节点，内存上限和节点分配失败也需要处理。

大规模构造还可以使用节点池减少逐节点分配开销，但池的生命周期必须覆盖整棵树，失败回滚也要释放或重置已分配区间。性能优化不能取消非法序列检查，否则更快地生成错误结构没有价值。

除遍历外还要检查什么

前序与中序回验能证明结果与输入一致，但业务节点可能还有父指针、高度、子树大小等派生字段。构造时若维护这些字段，测试还要逐节点验证：孩子的父指针指回当前节点，高度等于子树高度加一，子树大小等于左右大小之和加一。

序列只描述节点值与左右结构，不包含原对象身份、内存地址或额外元数据。所谓“重建原树”是重建同构的值与拓扑，不是恢复原节点对象。若身份有业务意义，遍历序列必须携带唯一ID和所需元数据。

构造完成后，最直接的黑盒验证是再次前序和中序遍历结果树，分别与输入比较。只画出一个样例或检查根值不能覆盖区间偏移错误；左右子树错接时，至少一种遍历会不同。

#include <cassert>
#include <vector>
 
void collect_preorder(
    const TreeNode* node,
    std::vector<int>& out
) {
    if (!node) return;
    out.push_back(node->value);
    collect_preorder(node->left.get(), out);
    collect_preorder(node->right.get(), out);
}
 
void test_regular_tree() {
    const std::vector<int> preorder{1,2,4,7,3,5,6,8};
    const std::vector<int> inorder{4,7,2,1,5,3,8,6};
    TreeBuilder builder;
    auto root = builder.build(preorder, inorder);
    std::vector<int> actual;
    collect_preorder(root.get(), actual);
    assert(actual == preorder);
}

还应实现collect_inorder并比较中序。官方七组测试覆盖普通树、全左、全右、单节点、完全二叉树、空指针和不匹配序列；优化版再增加重复值、长度不等和全局集合相同但局部区间冲突。

本章练习

练习

问题 1： 为什么前序和中序结合才能重建？

问题 2： 唯一值为什么是关键前提？

问题 3： 如何验证输入序列的合法性？

本章回顾

  1. 前序遍历按根、左、右访问，首项确定当前子树根。
  2. 中序遍历按左、根、右访问，根位置划分左右子树节点集合。
  3. 左子树长度决定前序根后多少元素属于左子树，剩余属于右子树。
  4. 递归区间必须长度相同、元素匹配，且根落在当前中序区间。
  5. 官方线性扫描定位根，退化树最坏O(n²)；中序索引表可把平均时间降为O(n)。
  6. 节点值重复会让根位置歧义，前序加中序不再保证唯一重建。
  7. unique_ptr让非法输入异常自动清理已构造子树。
  8. 递归栈空间O(h)，全左或全右树的高度为n。
  9. 重建后重新生成前序和中序，才能系统验证结构与输入一致。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

重建二叉树
从遍历序列恢复二叉树结构。
四个区间
前序和中序的左右子树范围。
唯一值
二叉树中节点值互不相同。
复习本章（10 题）

讨论

评论区加载中…