建模。桶数组 buckets_，每桶一条 pair 链；哈希函数用 Knuth 乘法哈希（键乘大奇数再截断）把整数打散；size_ 记元素数。不变量：\(\alpha = \text{size\_} / \text{buckets\_}.size() \le 1\)，即将越界时翻倍再哈希。

代码。

#include <cstddef>
#include <vector>
#include <list>
#include <utility>

class IntHashMap {
public:
    IntHashMap() : buckets_(8), size_(0) {}

    void put(int key, int value) {
        if (size_ + 1 > buckets_.size()) rehash();  // 维持装载因子 <= 1
        auto& chain = buckets_[index(key)];
        for (auto& kv : chain)
            if (kv.first == key) { kv.second = value; return; } // 覆盖旧值
        chain.push_back({key, value});
        ++size_;
    }

    bool get(int key, int& out) const {
        for (const auto& kv : buckets_[index(key)])
            if (kv.first == key) { out = kv.second; return true; }
        return false;
    }

private:
    static std::size_t hashInt(int key) {
        return (std::size_t)((unsigned long long)(unsigned)key * 2654435761u);
    }
    std::size_t index(int key) const {   // 桶下标 = 哈希对桶数取模
        return hashInt(key) % buckets_.size();
    }
    void rehash() {                       // 桶数翻倍，全部重新分布
        std::vector<std::list<std::pair<int,int>>> fresh(buckets_.size() * 2);
        for (auto& chain : buckets_)
            for (auto& kv : chain)
                fresh[hashInt(kv.first) % fresh.size()].push_back(kv);
        buckets_.swap(fresh);
    }

    std::vector<std::list<std::pair<int,int>>> buckets_;
    std::size_t size_;
};

数值演示。8 个桶、乘法哈希下依次 put(1,10)、put(9,90)：1 与 9 模 8 不同大概率不同桶，各自 O(1) 命中；若某键碰撞（如 1 与 9 恰同余），后者挂进同一条链，get 沿链线性比对。

复杂度。哈希均匀时期望 \(\Theta(1)\)：定位桶是取模，链长期望 \(\alpha \le 1\)。rehash 单次 \(\Theta(n)\)、均摊 \(\Theta(1)\)（论证与002 章倍增完全相同）。最坏 \(\Theta(n)\)：所有键同桶。

边界。负键：先转无符号再乘，避免有符号溢出的未定义行为；键覆盖（同键 put 更新而非重复插入）；开放寻址若改为本解必须处理删除（墓碑标记或周期性重建），链地址法无此负担——这也是教学实现选链地址的原因。

面试怎么讲。先写 \(\alpha = n/m\) 与「期望链长 \(\alpha\)」，再讲链地址与开放寻址的取舍，最后主动给最坏反例（同桶退化 O(n)）与工程对策（随机种子、链转红黑树）。这一套讲完，哈希表部分基本无可追问。

建模。错误做法是「每个节点与左右孩子比较」——它只验证局部，放过深层违规（见知识点反例：5 的右子树里出现 3）。正确做法有二：(a) 中序遍历必须严格递增；(b) 递归传递祖先上下界，每个节点的键必须落在开区间 \((lo, hi)\) 内。

代码（解法一：中序 + 前驱指针）。

bool inorder(TreeNode* node, TreeNode*& prev) {
    if (node == nullptr) return true;
    if (!inorder(node->left, prev)) return false;
    if (prev != nullptr && prev->val >= node->val)
        return false;                     // 中序必须严格递增
    prev = node;
    return inorder(node->right, prev);
}

bool isValidBST(TreeNode* root) {
    TreeNode* prev = nullptr;             // 中序里的前一个访问值
    return inorder(root, prev);
}

代码（解法二：上下界递归）。

#include <climits>
#include <cstdlib>

bool check(TreeNode* node, long long lo, long long hi) {
    if (node == nullptr) return true;
    if (node->val <= lo || node->val >= hi)
        return false;                     // 键必须落在开区间 (lo, hi)
    return check(node->left, lo, node->val) &&
           check(node->right, node->val, hi);
}
// 调用：check(root, LLONG_MIN, LLONG_MAX)

数值演示。树 [5,1,4,null,null,3,6]：节点 4 的左孩子 3 与 4 局部合法，但 3 在 5 的右子树中，违反「右子树全部大于 5」。解法一里中序序列 1,5,3,4,6 在 5 → 3 处递减，立即判负；解法二里 3 落在区间 \((5, 4)\) 外同样判负。两法结论一致：不是合法 BST。

复杂度。两解均为时间 \(O(n)\)（每节点访问一次）、空间 \(O(h)\) 递归栈，最坏链状 \(\Theta(n)\)。

边界。键取到 INT_MIN/INT_MAX 时解法二用 int 边界会误判，必须用 long long（或改传「前驱指针」从根上规避）；空树与单节点是合法 BST；相等键（重复值）按本题口径非法，比较必须用严格大于/小于。

面试怎么讲。先主动给出「只比孩子」的反例，展示你知道陷阱在哪，再写任一解法；说一句「中序有序是 BST 的充要条件」，把性质与算法连起来。

建模。递归中序隐式使用了调用栈；迭代化就是把「回来的路」显式放进一个栈。不变量：栈中从底到顶是「当前节点的一串祖先 + 各祖先的左链」；外层循环条件「curr 非空或栈非空」覆盖「正在下沉」与「正在回溯」两种状态。

代码。

#include <vector>
#include <stack>

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> order;
    std::stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {      // 沿左链一路下沉入栈
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();     // 左链尽头，弹出即最左未访问节点
        order.push_back(curr->val);    // 访问（左已尽，轮到根）
        curr = curr->right;            // 转向右子树，重复上述过程
    }
    return order;
}

数值演示。树 [1,null,2,3]（1 的右孩子 2，2 的左孩子 3）：下沉阶段只有 1 入栈；弹出访问 1；转向右子树 2，下沉 2 → 3 入栈；弹出访问 3，再弹出访问 2。输出 [1,3,2]，正是中序。

复杂度。时间 \(O(n)\)：每个节点恰好入栈、出栈各一次。空间 \(O(h)\)：栈深等于树高，平衡树 \(\Theta(\log n)\)，链状树 \(\Theta(n)\)。

边界。空树直接返回空；只有右链（一直不下沉直接弹出）与只有左链（一直下沉）是两个极端对拍用例。后序的迭代版可由「根右左再反转」得到：把本解的 left/right 交换得到根右左序，最后 reverse 一次。

面试怎么讲。讲不变量：「内层 while 负责下沉到最左，弹出即访问，然后去右子树」——三句话讲完循环结构再写代码，写错率最低。若被追问 Morris 遍历（线索化，\(O(1)\) 空间），能说出「用空闲右指针回指后继」的思想即可。

建模。前序第一个元素必是根；在中序里找到根的位置，其左边全是左子树的中序、右边全是右子树的中序；再由左子树的元素个数切出左子树的前序。递归下 go，子问题结构不变。用哈希表把「键 → 中序下标」预处理成 \(O(1)\) 查询。

代码。

#include <vector>
#include <unordered_map>

TreeNode* build(const std::vector<int>& pre, int pl, int pr, int il, int ir,
                std::unordered_map<int,int>& pos) {
    if (pl > pr) return nullptr;              // 空区间
    TreeNode* root = new TreeNode(pre[pl]);    // 前序首元素是根
    int k = pos[pre[pl]];                      // 根在中序中的切分点
    int leftLen = k - il;                      // 左子树元素个数
    root->left  = build(pre, pl + 1, pl + leftLen, il, k - 1, pos);
    root->right = build(pre, pl + leftLen + 1, pr, k + 1, ir, pos);
    return root;
}

TreeNode* buildTree(const std::vector<int>& pre, const std::vector<int>& in) {
    std::unordered_map<int,int> pos;          // 键 -> 中序下标
    for (int i = 0; i < (int)in.size(); ++i) pos[in[i]] = i;
    return build(pre, 0, (int)pre.size() - 1, 0, (int)in.size() - 1, pos);
}

数值演示。pre = [3,9,20,15,7]，in = [9,3,15,20,7]：根 3 在中序下标 1，左子树长度 1。左子树：pre[9]、in[9] → 叶子 9；右子树 pre[20,15,7]、in[15,20,7]：根 20，切分出左 15、右 7。重建结果与原树一致。

复杂度。时间 \(O(n)\)：每个节点建一次，切分点查询是哈希 \(O(1)\)（若不用哈希而在中序里线性找根，总代价退化到 \(O(n^2)\) 链状最坏）。空间 \(O(n)\) 哈希 + \(O(h)\) 递归栈。

边界。两数组必须同长且为同一棵树的有效遍历对（面试可声明此为前置条件，fail-fast 校验长度）；键必须互异，否则哈希映射歧义；只有左链或只有右链的树对应「左长度为 0」或「右长度为 0」的极端切分。顺带的知识点：后序 + 中序同样可重建（后序末元素是根），但前序 + 后序不能唯一重建——只有一个孩子的节点无法区分左右，这是高频追问。

面试怎么讲。先讲「前序定根、中序切左右」这一句核心，再讲用哈希把找根降到 O(1)，最后主动提「前序+后序不唯一」的反例，题目就完整了。