树

树题先确定"当前节点要完成什么"和"递归函数向父节点返回什么"。

遍历方式

遍历	访问顺序	常见用途
前序	根→左→右	构造、复制、序列化
中序	左→根→右	BST 有序遍历
后序	左→右→根	子树信息汇总、树形 DP、删除/释放
层序（BFS）	按层	层列表、最短层数、next 指针

层序遍历使用队列，并在每轮记录当前队列大小，才能分出每一层。

Morris 遍历：O(1) 辅助空间的前序、中序、后序

递归和显式栈会使用 O(h) 额外空间（h 为树高）。Morris 遍历临时把“当前节点左子树的最右节点”的空右指针连回当前节点，形成一条线索（thread），从而能在左子树结束后回到当前节点而无需栈。

对当前节点 cur：

1. 没有左孩子：访问 cur，转向 cur->right；
2. 有左孩子：找到左子树最右节点 pred；
   • pred->right == nullptr：第一次到达 cur，临时设 pred->right = cur，转入左子树；
   • pred->right == cur：第二次回到 cur，先断开 pred->right，再转入右子树。

前序和中序唯一的区别是“何时访问根”：第一次到达访问是前序，第二次回到访问是中序。

#include <vector>

struct TreeNode {
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};

std::vector<int> morris_preorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode* cur = root;

    while (cur != nullptr) {
        if (cur->left != nullptr) {
            // pre 是 cur 左子树的最右节点，
            // 即 cur 在中序遍历中的前驱。
            TreeNode* pre = cur->left;
            while (pre->right != nullptr && pre->right != cur) {
                pre = pre->right;
            }

            if (pre->right == nullptr) {
                // 第一次到达 cur：前序先访问根，再建立线索进入左子树。
                result.push_back(cur->val);
                pre->right = cur;
                cur = cur->left;
                continue;
            }

            // 第二次回到 cur：左子树已完成，必须拆除线索。
            // cur 已在第一次到达时访问过，不能重复记录。
            pre->right = nullptr;
        } else {
            // 没有左子树：这是第一次也是唯一一次到达 cur，直接访问。
            result.push_back(cur->val);
        }

        cur = cur->right;
    }

    return result;
}

std::vector<int> morris_inorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode* cur = root;

    while (cur != nullptr) {
        if (cur->left != nullptr) {
            // pre 是 cur 左子树的最右节点，
            // 即 cur 在中序遍历中的前驱。
            TreeNode* pre = cur->left;
            while (pre->right != nullptr && pre->right != cur) {
                pre = pre->right;
            }

            if (pre->right == nullptr) {
                // 第一次到达 cur：建立线索并进入左子树。
                pre->right = cur;
                cur = cur->left;
                continue;
            }

            // 第二次回到 cur：左子树已完成，
            // 必须拆除线索，恢复原二叉树结构。
            pre->right = nullptr;
        }

        // 左子树为空或已完成：访问根，再进入右子树。
        result.push_back(cur->val);
        cur = cur->right;
    }

    return result;
}

后序要求“左 → 右 → 根”，不能只调整访问 cur 的时机。做法是建立一个虚拟根，并在第二次回到节点时，反转其左子树右边界，沿反转后的链访问，再立即反转回来：

// 反转 from 到 to（含）的 right 指针；调用方保证 to 沿 right 可达。
void reverse_right_edge(TreeNode* from, TreeNode* to) {
    TreeNode* prev = nullptr;
    TreeNode* cur = from;

    while (prev != to) {
        TreeNode* next = cur->right;
        cur->right = prev;
        prev = cur;
        cur = next;
    }
}

std::vector<int> morris_postorder(TreeNode* root) {
    std::vector<int> result;
    TreeNode dummy{0, root, nullptr};         // 保证原根也会被统一处理
    TreeNode* cur = &dummy;

    while (cur != nullptr) {
        if (cur->left != nullptr) {
            TreeNode* pre = cur->left;
            while (pre->right != nullptr && pre->right != cur) {
                pre = pre->right;
            }

            if (pre->right == nullptr) {
                // 第一次到达 cur：建立线索并进入左子树。
                pre->right = cur;
                cur = cur->left;
                continue;
            }

            // 第二次回到 cur：左子树已经完成。反转右边界后访问，
            // 其顺序正好是这棵左子树的后序输出顺序。
            reverse_right_edge(cur->left, pre);
            for (TreeNode* node = pre;; node = node->right) {
                result.push_back(node->val);
                if (node == cur->left) {
                    break;
                }
            }
            reverse_right_edge(pre, cur->left); // 必须恢复右边界
            pre->right = nullptr;               // 删除线索
        }

        // 左子树为空或已完成：继续处理右子树。
        cur = cur->right;
    }

    return result;
}

三种算法均为 O(n) 时间、O(1) 辅助空间。寻找 pred 的循环看似会重复扫描，但每条边只会被沿正反方向经过常数次，因此总时间仍是 O(n)。

重要边界：Morris 会暂时修改树的 right 指针，代码必须在所有正常路径上恢复线索和反转边界。不要在遍历中提前 return、让访问回调抛异常，或并发暴露这棵树；否则树可能被留下环或错误链接。一般业务代码优先递归或显式栈，只有题目严格要求 O(1) 辅助空间、且可独占修改树时才选 Morris。

返回值的两种风格

• 只需遍历并通过引用/成员变量累计结果：递归函数可返回 void；
• 需要向父节点传递"是否找到""子树高度""可继续向上的路径"等信息：返回 bool、数值、指针或状态结构。

例如最近公共祖先（LCA）的后序递归：左右子树分别返回 p/q 或它们的 LCA；若左右均非空，当前节点就是 LCA。

二叉搜索树（BST）

二叉搜索树（Binary Search Tree，BST）把“可比较的键”按大小组织成二叉树，用于动态维护有序集合或映射。它不是“节点左孩子比节点小、右孩子比节点大”这么简单，而是一个子树范围不变量：对任意节点 x，x 的左子树中所有键都小于 x.key，右子树中所有键都大于 x.key。

        8
       / \
      3  10
       \
        9     ← 9 < 10，却出现在 8 的左子树；整棵树不是 BST

BST 不要求是完全二叉树，也不天然平衡；“二叉树”不等于“BST”，而“最大堆”也不是 BST（堆只约束父子关系，不能支持有序查找）。

重复键规则

实现前必须确定重复键如何处理，否则插入、验证、删除和中序遍历的规则会互相矛盾：

• 集合（set）语义：键已存在就不插入；下文的实现采用该规则；
• 计数语义：每个节点维护 count，相同键只增加计数；
• 固定方向：例如左子树 < key、右子树 >= key。这也可行，但验证边界、删除和范围查询都必须严格遵循同一规则。

为什么操作只走一条路径

以查找 key 为例：若 key < node->val，目标若存在只能在左子树；若更大只能在右子树。插入、删除、最小值、最大值、前驱和后继也都利用这一性质，因此成本由树高 h 决定：

操作	时间复杂度	说明
查找 / 插入 / 删除	O(h)	每一步只进入一个孩子
最小值 / 最大值	O(h)	分别一直向左 / 向右
lower_bound、前驱、后继	O(h)	沿路径维护候选答案
范围查询 [low, high]	O(h + k)	定位和剪枝 O(h)，输出 k 个元素
中序遍历	O(n)	按升序访问所有节点
空间	O(n)	n 个节点；递归额外 O(h)

普通 BST 在随机或较均衡输入下通常有 h = O(log n)；若连续按升序插入 1, 2, 3, ...，会退化成链表，所有基本操作变为 O(n)。需要最坏 O(log n) 保证时，应使用 AVL 树或红黑树。

查找、插入与上下界

以下以“不允许重复键”的 TreeNode 为例。查找和插入既可递归写，也可迭代写；迭代能避免普通 BST 退化时的深递归栈。

struct TreeNode {
    explicit TreeNode(int value) : val(value) {}

    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};

TreeNode* find(TreeNode* root, int key) {
    while (root) {
        if (key < root->val) root = root->left;
        else if (key > root->val) root = root->right;
        else return root;
    }
    return nullptr;
}

// 返回根；若 key 已存在，保持树不变。
TreeNode* insert(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);

    TreeNode* current = root;
    while (true) {
        if (key < current->val) {
            if (!current->left) {
                current->left = new TreeNode(key);
                break;
            }
            current = current->left;
        } else if (key > current->val) {
            if (!current->right) {
                current->right = new TreeNode(key);
                break;
            }
            current = current->right;
        } else {
            break; // set 语义：忽略重复键
        }
    }
    return root;
}

// 返回最小的 >= key 的节点；不存在时返回 nullptr。
TreeNode* lower_bound(TreeNode* root, int key) {
    TreeNode* answer = nullptr;
    while (root) {
        if (root->val >= key) {
            answer = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return answer;
}

最小值是“从当前节点一路向左”，最大值反之。节点 x 的后继：若右子树存在，取右子树的最左节点；否则向上寻找第一个把 x 放在其左子树中的祖先。前驱与之对称。没有父指针时，可从根向下并维护候选祖先；有父指针时可直接向上走。

删除：三种结构情况

删除是 BST 最容易写错的操作。先像查找一样定位节点，再根据孩子数量处理：

1. 叶节点：直接删除，父节点对应指针设为空；
2. 仅一个孩子：让父节点直接指向这个孩子；
3. 两个孩子：用右子树最小节点（中序后继）或左子树最大节点（中序前驱）覆盖当前键，然后在对应子树中删除那个后继/前驱节点。后继至多只有一个右孩子，因此递归会落到前两种简单情况。

TreeNode* min_node(TreeNode* root) {
    while (root->left) root = root->left;
    return root;
}

// 此函数拥有并释放被删节点；调用方必须遵循同一所有权约定。
TreeNode* erase(TreeNode* root, int key) {
    if (!root) return nullptr;

    if (key < root->val) {
        root->left = erase(root->left, key);
    } else if (key > root->val) {
        root->right = erase(root->right, key);
    } else {
        if (!root->left) {
            TreeNode* replacement = root->right;
            delete root;
            return replacement;
        }
        if (!root->right) {
            TreeNode* replacement = root->left;
            delete root;
            return replacement;
        }

        TreeNode* successor = min_node(root->right);
        root->val = successor->val;                 // 保持当前节点连接不变
        root->right = erase(root->right, successor->val);
    }
    return root;
}

不能把“后继节点指针”直接赋给当前节点后就删除整个右子树，否则可能丢失后继原有的右孩子或造成重复连接。算法题若由平台统一管理节点，需遵守题目给定的内存所有权约定；生产代码优先用 std::unique_ptr 等 RAII 所有权表达节点关系。

验证、遍历与有序查询

只检查父节点和直接孩子会漏掉跨层违法节点，验证应把祖先给出的开区间一路传递。这里的严格不等号对应“禁止重复键”的策略：

#include <limits>

bool is_valid_bst(const TreeNode* node, long long low, long long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return is_valid_bst(node->left, low, node->val)
        && is_valid_bst(node->right, node->val, high);
}

bool is_valid_bst(const TreeNode* root) {
    return is_valid_bst(root,
                        std::numeric_limits<long long>::lowest(),
                        std::numeric_limits<long long>::max());
}

BST 的中序遍历输出严格递增序列（若允许重复键，则为非递减序列）。这使它特别适合：第 k 小元素（中序第 k 个）、[low, high] 范围枚举、前驱/后继、按键排序输出。范围遍历时可剪枝：node->val < low 就无需进入左子树；node->val > high 就无需进入右子树。

面试易错点

1. 复杂度应答 O(h)；未经平衡的 BST 不能直接回答 O(log n)；
2. 验证 BST 需要上下界或中序全局递增，不能只比较直接孩子；
3. 后继是“右子树最左节点”，不一定就是右孩子；
4. 双孩子删除后，要在右子树中继续删除后继，不能只覆盖值而留下重复键；
5. 重复键策略必须贯穿插入、验证和删除；
6. 大量升序输入会退化，递归版本可能同时出现 O(n) 时间和 O(n) 调用栈。

构造、序列化与树形 DP

• 前序 + 中序构树：前序首元素是根；在中序中定位根，左右部分的长度决定前序切分。若值唯一，可先建立"值→中序下标"哈希表，将复杂度从 O(n²) 降为 O(n)；
• 中序 + 后序构树：后序末元素是根，其他切分同理；
• 最大二叉树：区间最大值为根；朴素递归最坏 O(n²)，单调栈可优化到 O(n)；
• 重复子树：后序生成带空节点标记的结构 ID/序列化，哈希统计出现次数；为避免重复收集，计数从 1 变为 2 时加入答案；
• 树形 DP：后序返回有限状态。例如打家劫舍 III 可返回 {不选当前节点的最大值, 选当前节点的最大值}，避免重复递归。

二叉树最深可能退化为 O(n)，递归在极深输入下有栈风险；需要时改用显式栈实现 DFS。

关联笔记

• 链表
• 图搜索、回溯与并查集
• 递归、显式栈与字符串解码