4. 二叉树 | Jiayu Lab

ABSTRACT · 本节范围本笔记逐页覆盖原 PDF 的 30 页内容和 33 道实际题目。源文件题号依次为 1～17、19～29、31～35，原稿本身没有第 18、30 题；第 33 题只有题干、没有答案，本文已补全。代码统一为 C++17，并将原稿中的指针传递、左右子树、回溯、释放、队列边界和线索标志错误全部订正。

0. 公共定义与解题框架

#include <algorithm>
#include <cstddef>
#include <optional>
#include <queue>
#include <stack>
#include <stdexcept>
#include <utility>
#include <vector>

struct BTNode {
    int data{};
    BTNode* left = nullptr;
    BTNode* right = nullptr;
};

递归题先回答三个问题：

空树返回什么；
当前结点贡献什么；
左右子树结果如何合并。

非递归题则明确栈或队列里保存的是“待访问结点”还是“当前路径”，并写清入栈、出栈和分层边界。以下约定根结点位于第 1 层；涉及 WPL 时，根的路径长度为 0。

1. 递归统计与基本性质

题 1：统计全部结点数

空树为 0；非空树等于左子树结点数、右子树结点数再加根结点。

题 2：统计叶结点数

只有左右孩子都为空的结点才是叶结点。空树不贡献叶子。

题 3：统计双分支结点数

当前结点左右孩子均非空时贡献 1，否则只合并左右子树结果。

题 4：计算二叉树深度

空树高度为 0；非空树高度为左右子树较大高度加 1。

std::size_t nodeCount(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return nodeCount(root->left) + nodeCount(root->right) + 1;
}

std::size_t leafCount(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    return leafCount(root->left) + leafCount(root->right);
}

std::size_t degreeTwoCount(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }
    const std::size_t self =
        (root->left != nullptr && root->right != nullptr) ? 1 : 0;
    return self + degreeTwoCount(root->left)
                + degreeTwoCount(root->right);
}

std::size_t treeHeight(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return std::max(treeHeight(root->left),
                    treeHeight(root->right)) + 1;
}

四个函数都访问每个结点一次，时间复杂度 $O(n)$；递归栈空间为 $O(h)$，其中 $h$ 是树高，最坏为 $O(n)$。

DANGER · 原稿错误题 1 的操作型代码和题 4 的操作型代码都把左右递归写成了两次左子树；题 4 还把函数右花括号放到了主体之前。计算型递归更短，也不会出现“回溯时忘记恢复深度”的问题。

2. 表达式、最值、相似与镜像

题 5：计算表达式树

叶结点保存操作数，分支结点保存运算符。先递归得到左右操作数，再按当前运算符组合；减法和除法必须保持左右次序。

struct ExprNode {
    bool isOperand = true;
    double value = 0.0;
    char op = '\0';
    ExprNode* left = nullptr;
    ExprNode* right = nullptr;
};

double evaluateExpression(const ExprNode* root) {
    if (root == nullptr) {
        throw std::invalid_argument("expression tree is incomplete");
    }
    if (root->isOperand) {
        return root->value;
    }

    const double lhs = evaluateExpression(root->left);
    const double rhs = evaluateExpression(root->right);
    switch (root->op) {
        case '+': return lhs + rhs;
        case '-': return lhs - rhs;
        case '*': return lhs * rhs;
        case '/':
            if (rhs == 0.0) {
                throw std::domain_error("division by zero");
            }
            return lhs / rhs;
        default:
            throw std::invalid_argument("unknown operator");
    }
}

原题给出的 (a-(b+c))*(d/e) 对应根运算符 *，左子树为 a-(b+c)，右子树为 d/e。若叶子保存变量名，应先由符号表取得变量值，再执行同样的后序求值。

题 6：找出最大值结点

不应要求调用者猜一个“足够小”的初值；直接把当前根作为候选，再与左右子树候选比较。

题 7：判断两棵二叉树是否相似

本题“相似”只比较结构，不比较数据：两结点都空为真，仅一方为空为假，两方非空则对应左右子树都要相似。

题 8：交换所有结点的左右子树

每个非空结点只需交换一次左右指针。先递归后交换或先交换后递归都正确，但不能重复处理同一孩子。

const BTNode* maxNode(const BTNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

    const BTNode* best = root;
    const BTNode* leftBest = maxNode(root->left);
    const BTNode* rightBest = maxNode(root->right);
    if (leftBest != nullptr && leftBest->data > best->data) {
        best = leftBest;
    }
    if (rightBest != nullptr && rightBest->data > best->data) {
        best = rightBest;
    }
    return best;
}

bool structurallySimilar(const BTNode* first, const BTNode* second) {
    if (first == nullptr || second == nullptr) {
        return first == second;
    }
    return structurallySimilar(first->left, second->left)
        && structurallySimilar(first->right, second->right);
}

void mirrorTree(BTNode* root) {
    if (root == nullptr) {
        return;
    }
    std::swap(root->left, root->right);
    mirrorTree(root->left);
    mirrorTree(root->right);
}

DANGER · 原稿错误题 5 的 return 位置、结点变量名和运算函数均不完整；题 6 把左右递归放进了“当前值更大”分支，导致当前根没有刷新最大值时整棵子树都不会继续搜索。

3. 查找、删除、叶链表与路径

题 9：查找 `data == key` 的结点

先序检查当前结点，命中立即返回；左子树命中后也必须逐层传播结果，不能继续无意义地搜索右子树。

题 10：取得先序遍历第 $k$ 个结点

计数从 1 开始。k == 0 或树中不足 $k$ 个结点时返回空指针。

题 11：求值为 $x$ 的结点层号

根层号为 1；返回 0 表示未找到。若关键字可能重复，下列算法返回先序遇到的第一个结点层号。

BTNode* findFirstPreorder(BTNode* root, int key) {
    if (root == nullptr || root->data == key) {
        return root;
    }
    if (BTNode* found = findFirstPreorder(root->left, key)) {
        return found;
    }
    return findFirstPreorder(root->right, key);
}

const BTNode* kthPreorderImpl(const BTNode* root,
                             std::size_t k,
                             std::size_t& visited) {
    if (root == nullptr) {
        return nullptr;
    }
    if (++visited == k) {
        return root;
    }
    if (const BTNode* found =
            kthPreorderImpl(root->left, k, visited)) {
        return found;
    }
    return kthPreorderImpl(root->right, k, visited);
}

const BTNode* kthPreorder(const BTNode* root, std::size_t k) {
    if (k == 0) {
        return nullptr;
    }
    std::size_t visited = 0;
    return kthPreorderImpl(root, k, visited);
}

int levelOf(const BTNode* root, int key, int level = 1) {
    if (root == nullptr) {
        return 0;
    }
    if (root->data == key) {
        return level;
    }
    const int leftLevel = levelOf(root->left, key, level + 1);
    return leftLevel != 0
        ? leftLevel
        : levelOf(root->right, key, level + 1);
}

DANGER · 原稿错误题 9 把结果指针按值传入，函数返回后调用者仍得到空指针；题 10 命中后只结束当前调用，祖先仍可能继续遍历；题 11 又把左右递归写成两次左子树，并且引用深度在提前返回时无法可靠恢复。

题 12：删除值为 $x$ 的结点及其整棵子树

“删除子树”不仅要断开父结点指针，还要后序释放所有后代。指向子树根的指针必须按引用传递。

void destroyTree(BTNode*& root) {
    if (root == nullptr) {
        return;
    }
    destroyTree(root->left);
    destroyTree(root->right);
    delete root;
    root = nullptr;
}

void deleteSubtreesByKey(BTNode*& root, int key) {
    if (root == nullptr) {
        return;
    }
    if (root->data == key) {
        destroyTree(root);
        return;
    }
    deleteSubtreesByKey(root->left, key);
    deleteSubtreesByKey(root->right, key);
}

如果关键字重复，该实现会删除先序搜索过程中遇到的每一棵匹配子树；某棵子树根已匹配时，其后代自然随整棵子树释放，不再单独搜索。

题 13：用叶结点右指针串成单链表

按从左到右的叶序列链接，head 指向第一个叶结点，tail 始终指向最后一个叶结点。两者必须按引用传递。

void linkLeavesImpl(BTNode* root, BTNode*& head, BTNode*& tail) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        if (head == nullptr) {
            head = root;
        } else {
            tail->right = root;
        }
        tail = root;
        tail->right = nullptr;
        return;
    }
    linkLeavesImpl(root->left, head, tail);
    linkLeavesImpl(root->right, head, tail);
}

BTNode* linkLeavesLeftToRight(BTNode* root) {
    BTNode* head = nullptr;
    BTNode* tail = nullptr;
    linkLeavesImpl(root, head, tail);
    return head;
}

WARNING · 破坏性本题明确复用叶结点的右孩子指针，因此转换后原结构不再是一棵普通二叉树。若还要保留原树，应另建链表结点或只返回叶结点指针数组。

题 14：输出根到每个叶结点的路径

进入结点时压入当前路径；无论当前结点是否为叶子，离开前都必须弹出，保证回溯后的路径状态与进入前一致。

void collectRootToLeafPaths(
        const BTNode* root,
        std::vector<int>& current,
        std::vector<std::vector<int>>& paths) {
    if (root == nullptr) {
        return;
    }

    current.push_back(root->data);
    if (root->left == nullptr && root->right == nullptr) {
        paths.push_back(current);
    } else {
        collectRootToLeafPaths(root->left, current, paths);
        collectRootToLeafPaths(root->right, current, paths);
    }
    current.pop_back();
}

std::vector<std::vector<int>> rootToLeafPaths(const BTNode* root) {
    std::vector<std::vector<int>> paths;
    std::vector<int> current;
    collectRootToLeafPaths(root, current, paths);
    return paths;
}

原稿只在“非叶结点”分支执行出栈，访问第一个叶子后路径会残留，后续路径全部被污染。

4. 由序列构造或转换二叉树

题 15：满二叉树先序序列转后序序列

这里的“满二叉树”按 408 中文定义指每层都满的完美二叉树，结点数为 $2^h-1$。当前先序段首元是根，其余结点可等分为左右子树；分别递归后再追加根，即得到后序。

void perfectPreToPostImpl(const std::vector<int>& preorder,
                          std::size_t left,
                          std::size_t right,
                          std::vector<int>& postorder) {
    if (left == right) {
        postorder.push_back(preorder[left]);
        return;
    }

    const std::size_t childSize = (right - left) / 2;
    perfectPreToPostImpl(preorder, left + 1,
                        left + childSize, postorder);
    perfectPreToPostImpl(preorder, left + childSize + 1,
                        right, postorder);
    postorder.push_back(preorder[left]);
}

std::vector<int> perfectPreorderToPostorder(
        const std::vector<int>& preorder) {
    if (preorder.empty()) {
        return {};
    }
    if ((preorder.size() & (preorder.size() + 1)) != 0) {
        throw std::invalid_argument(
            "a perfect tree must have 2^h - 1 nodes");
    }

    std::vector<int> postorder;
    postorder.reserve(preorder.size());
    perfectPreToPostImpl(preorder, 0, preorder.size() - 1,
                         postorder);
    return postorder;
}

IMPORTANT · 适用前提若“满”仅表示每个分支结点都有两个孩子、但各叶子不在同一层，左右子树规模不能由先序长度直接等分；仅凭先序也不能唯一推出后序。

题 16：由先序和中序序列建立二叉树

关键字互异时可唯一确定：先序首元为根，在中序中定位根，根左侧长度决定先序中左子树的范围。

BTNode* buildPreInImpl(const std::vector<int>& preorder,
                       int preLeft,
                       int preRight,
                       const std::vector<int>& inorder,
                       int inLeft,
                       int inRight) {
    if (preLeft > preRight) {
        return nullptr;
    }

    const int rootValue = preorder[preLeft];
    const auto begin = inorder.begin() + inLeft;
    const auto end = inorder.begin() + inRight + 1;
    const auto position = std::find(begin, end, rootValue);
    if (position == end) {
        throw std::invalid_argument("inconsistent traversals");
    }

    const int rootIndex =
        static_cast<int>(position - inorder.begin());
    const int leftSize = rootIndex - inLeft;
    BTNode* root = new BTNode{rootValue, nullptr, nullptr};
    try {
        root->left = buildPreInImpl(
            preorder, preLeft + 1, preLeft + leftSize,
            inorder, inLeft, rootIndex - 1);
        root->right = buildPreInImpl(
            preorder, preLeft + leftSize + 1, preRight,
            inorder, rootIndex + 1, inRight);
    } catch (...) {
        destroyTree(root);  // 输入不一致时回收已经建好的部分树。
        throw;
    }
    return root;
}

BTNode* buildFromPreorderInorder(
        const std::vector<int>& preorder,
        const std::vector<int>& inorder) {
    if (preorder.size() != inorder.size()) {
        throw std::invalid_argument("traversal sizes differ");
    }
    if (preorder.empty()) {
        return nullptr;
    }
    return buildPreInImpl(
        preorder, 0, static_cast<int>(preorder.size()) - 1,
        inorder, 0, static_cast<int>(inorder.size()) - 1);
}

线性查找中序根位置的最坏时间为 $O(n^2)$；若预先建立“关键字到中序下标”的散列表，可降为 $O(n)$。关键字重复时还需额外规则，否则不能唯一确定。输入序列不一致而在递归中抛错时，已创建的部分树会先被释放。

题 17：由顺序存储建立链式二叉树

0 下标数组中，结点 $i$ 的左右孩子位置分别为 $2i+1$ 和 $2i+2$。普通二叉树的顺序表示必须保留空位置，所以下列代码用 std::optional 表示空结点。

BTNode* buildFromSequential(
        const std::vector<std::optional<int>>& sequence,
        std::size_t index = 0) {
    if (index >= sequence.size() || !sequence[index].has_value()) {
        return nullptr;
    }

    BTNode* root =
        new BTNode{*sequence[index], nullptr, nullptr};
    root->left =
        buildFromSequential(sequence, index * 2 + 1);
    root->right =
        buildFromSequential(sequence, index * 2 + 2);
    return root;
}

原稿把右孩子递归结果再次赋给 lchild，会覆盖已经建立的左子树；同时没有说明普通二叉树数组里的空位表示。

NOTE · 关于题号 18 原 PDF 在题 17 后直接进入题 19，文件中不存在题 18 的题干或答案。本笔记没有把它误当成待补内容。

5. 非递归遍历、祖先与最近公共祖先

题 19：非递归先序遍历

弹出即访问。为了让左子树先出栈，必须先压右孩子、再压左孩子。

题 20：非递归中序遍历

不断沿左链压栈；无左路可走时弹栈访问，再转向右子树。

题 21：非递归后序遍历

栈保存根到当前结点的路径，lastVisited 记录最近完成访问的结点。若栈顶右子树存在且尚未访问，先转向右子树；否则访问栈顶。

std::vector<int> preorderIterative(const BTNode* root) {
    std::vector<int> order;
    if (root == nullptr) {
        return order;
    }

    std::stack<const BTNode*> pending;
    pending.push(root);
    while (!pending.empty()) {
        const BTNode* node = pending.top();
        pending.pop();
        order.push_back(node->data);
        if (node->right != nullptr) {
            pending.push(node->right);
        }
        if (node->left != nullptr) {
            pending.push(node->left);
        }
    }
    return order;
}

std::vector<int> inorderIterative(const BTNode* root) {
    std::vector<int> order;
    std::stack<const BTNode*> path;
    const BTNode* current = root;

    while (current != nullptr || !path.empty()) {
        while (current != nullptr) {
            path.push(current);
            current = current->left;
        }
        current = path.top();
        path.pop();
        order.push_back(current->data);
        current = current->right;
    }
    return order;
}

std::vector<int> postorderIterative(const BTNode* root) {
    std::vector<int> order;
    std::stack<const BTNode*> path;
    const BTNode* current = root;
    const BTNode* lastVisited = nullptr;

    while (current != nullptr || !path.empty()) {
        if (current != nullptr) {
            path.push(current);
            current = current->left;
        } else {
            const BTNode* top = path.top();
            if (top->right != nullptr
                    && lastVisited != top->right) {
                current = top->right;
            } else {
                order.push_back(top->data);
                lastVisited = top;
                path.pop();
            }
        }
    }
    return order;
}

三种遍历均为时间 $O(n)$、辅助栈 $O(h)$。原稿的先序代码没有访问语句；后序代码在当前指针可能为空时直接读取 bt->lchild，会空指针解引用。

题 22：输出值为 $x$ 的结点的全部祖先

把根到目标的完整路径保存下来，去掉最后的目标结点，剩余部分即为从根到父结点的祖先序列。

bool findPathTo(const BTNode* root,
                int key,
                std::vector<const BTNode*>& path) {
    if (root == nullptr) {
        return false;
    }

    path.push_back(root);
    if (root->data == key
            || findPathTo(root->left, key, path)
            || findPathTo(root->right, key, path)) {
        return true;
    }
    path.pop_back();
    return false;
}

bool ancestorsOf(const BTNode* root,
                 int key,
                 std::vector<int>& ancestors) {
    ancestors.clear();
    std::vector<const BTNode*> path;
    if (!findPathTo(root, key, path)) {
        return false;
    }
    for (std::size_t i = 0; i + 1 < path.size(); ++i) {
        ancestors.push_back(path[i]->data);
    }
    return true;
}

返回 true 且结果为空可能表示目标就是根；返回 false 才表示树中没有目标。

题 23：求结点 $p,q$ 的最近公共祖先

若当前根分别从左右递归得到非空结果，说明两目标分居两侧，当前根就是最近公共祖先；若只一侧非空，则答案继续向上返回。公开函数先确认两个目标都在树中，避免只存在一个结点时误把它当成答案。

bool containsNode(const BTNode* root, const BTNode* target) {
    if (root == nullptr || target == nullptr) {
        return false;
    }
    return root == target
        || containsNode(root->left, target)
        || containsNode(root->right, target);
}

const BTNode* lcaImpl(const BTNode* root,
                      const BTNode* first,
                      const BTNode* second) {
    if (root == nullptr || root == first || root == second) {
        return root;
    }

    const BTNode* left =
        lcaImpl(root->left, first, second);
    const BTNode* right =
        lcaImpl(root->right, first, second);
    if (left != nullptr && right != nullptr) {
        return root;
    }
    return left != nullptr ? left : right;
}

const BTNode* lowestCommonAncestor(
        const BTNode* root,
        const BTNode* first,
        const BTNode* second) {
    if (!containsNode(root, first)
            || !containsNode(root, second)) {
        return nullptr;
    }
    return lcaImpl(root, first, second);
}

原稿复制祖先栈时混用了 top/top1，比较时又把 stack1 与工作栈 stack 混用；双重循环首次相等也不保证取到“最近”的公共祖先。

6. 层次遍历、宽度、高度、完全性与 WPL

题 24：层次遍历

根入队；每次出队访问当前结点，再依次把非空左、右孩子入队。

题 25：自下而上、从右到左的层次遍历

普通层次遍历得到“自上而下、从左到右”的总序列，将整个序列逆置，层次次序和每层内部次序会同时反转，恰好得到题目要求。

std::vector<int> levelOrder(const BTNode* root) {
    std::vector<int> order;
    if (root == nullptr) {
        return order;
    }

    std::queue<const BTNode*> pending;
    pending.push(root);
    while (!pending.empty()) {
        const BTNode* node = pending.front();
        pending.pop();
        order.push_back(node->data);
        if (node->left != nullptr) {
            pending.push(node->left);
        }
        if (node->right != nullptr) {
            pending.push(node->right);
        }
    }
    return order;
}

std::vector<int> bottomUpRightToLeft(const BTNode* root) {
    std::vector<int> order = levelOrder(root);
    std::reverse(order.begin(), order.end());
    return order;
}

原稿题 25 把 bt->data 放入“结点指针队列”，随后又当作结点指针出队，类型不一致；栈对象还混用了 .、-> 和未限定的 top。

题 26：求二叉树最大宽度

每轮开始时，队列长度就是当前层结点数；处理恰好这么多个结点并把下一层入队，更新最大值即可。

题 27：用层次遍历求树高

每处理完一层，高度加 1。空树高度为 0。

std::size_t maximumWidth(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }

    std::queue<const BTNode*> pending;
    pending.push(root);
    std::size_t best = 0;
    while (!pending.empty()) {
        const std::size_t levelSize = pending.size();
        best = std::max(best, levelSize);
        for (std::size_t i = 0; i < levelSize; ++i) {
            const BTNode* node = pending.front();
            pending.pop();
            if (node->left != nullptr) {
                pending.push(node->left);
            }
            if (node->right != nullptr) {
                pending.push(node->right);
            }
        }
    }
    return best;
}

std::size_t treeHeightByLevel(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }

    std::queue<const BTNode*> pending;
    pending.push(root);
    std::size_t height = 0;
    while (!pending.empty()) {
        const std::size_t levelSize = pending.size();
        ++height;
        for (std::size_t i = 0; i < levelSize; ++i) {
            const BTNode* node = pending.front();
            pending.pop();
            if (node->left != nullptr) {
                pending.push(node->left);
            }
            if (node->right != nullptr) {
                pending.push(node->right);
            }
        }
    }
    return height;
}

原稿题 26 的层号写入发生在 rear++ 之后，写到了错误位置，换层时还把计数清零后才比较；题 27 的 last 没有初始化。直接使用每层队列长度能避开这些下标错误。

题 28：判断完全二叉树

层次遍历把空孩子也入队。一旦出现第一个空位置，后面只能继续出现空位置；若之后又出现非空结点，就违反完全二叉树“结点从左到右连续”的条件。

bool isCompleteBinaryTree(const BTNode* root) {
    if (root == nullptr) {
        return true;
    }

    std::queue<const BTNode*> pending;
    pending.push(root);
    bool seenEmptyPosition = false;
    while (!pending.empty()) {
        const BTNode* node = pending.front();
        pending.pop();
        if (node == nullptr) {
            seenEmptyPosition = true;
        } else {
            if (seenEmptyPosition) {
                return false;
            }
            pending.push(node->left);
            pending.push(node->right);
        }
    }
    return true;
}

原稿空树判断写成 bt == true，既不表达空指针，也会产生错误语义。

题 29：计算叶结点带权路径长度

若根深度为 0，深度 $d$ 的叶结点权值 $w$ 对 WPL 的贡献为 $wd$：

$$ \operatorname{WPL}=\sum_{\text{叶 }i} w_i d_i. $$

long long weightedPathLength(const BTNode* root, int depth = 0) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return static_cast<long long>(root->data) * depth;
    }
    return weightedPathLength(root->left, depth + 1)
         + weightedPathLength(root->right, depth + 1);
}

long long weightedPathLengthByLevel(const BTNode* root) {
    if (root == nullptr) {
        return 0;
    }

    std::queue<std::pair<const BTNode*, int>> pending;
    pending.push({root, 0});
    long long result = 0;
    while (!pending.empty()) {
        const auto [node, depth] = pending.front();
        pending.pop();
        if (node->left == nullptr && node->right == nullptr) {
            result += static_cast<long long>(node->data) * depth;
        } else {
            if (node->left != nullptr) {
                pending.push({node->left, depth + 1});
            }
            if (node->right != nullptr) {
                pending.push({node->right, depth + 1});
            }
        }
    }
    return result;
}

两种写法均为时间 $O(n)$。递归辅助空间 $O(h)$；层次法辅助空间 $O(w)$，其中 $w$ 是最大宽度。原稿层次法混用了未声明的 deep 和 level，层边界 last 的初值也不一致。

NOTE · 关于题号 30 原 PDF 在题 29 后直接进入题 31，文件中不存在题 30。

7. 线索二叉树、二叉搜索树与孩子兄弟树

题 31：建立中序线索二叉树

Child 表示指针指向真实孩子，Thread 表示指针是前驱或后继线索。中序遍历时：

当前结点无左孩子，就把左指针改为前驱线索；
前驱结点无右孩子，就把前驱的右指针改为当前结点的后继线索。

enum class PointerTag {
    Child,
    Thread
};

struct ThreadNode {
    int data{};
    ThreadNode* left = nullptr;
    ThreadNode* right = nullptr;
    PointerTag leftTag = PointerTag::Child;
    PointerTag rightTag = PointerTag::Child;
};

void inorderThreadImpl(ThreadNode* root, ThreadNode*& previous) {
    if (root == nullptr) {
        return;
    }

    inorderThreadImpl(root->left, previous);
    if (root->left == nullptr) {
        root->leftTag = PointerTag::Thread;
        root->left = previous;
    }
    if (previous != nullptr && previous->right == nullptr) {
        previous->rightTag = PointerTag::Thread;
        previous->right = root;
    }
    previous = root;
    inorderThreadImpl(root->right, previous);
}

void createInorderThreads(ThreadNode* root) {
    ThreadNode* previous = nullptr;
    inorderThreadImpl(root, previous);
    if (previous != nullptr && previous->right == nullptr) {
        previous->rightTag = PointerTag::Thread;
        previous->right = nullptr;
    }
}

该函数的前置条件是“尚未线索化的普通二叉树，两个标志均为 Child”。线索化后不能再用忽略标志的普通递归遍历，否则会沿前驱、后继线索形成重复访问。

题 32：中序遍历线索二叉树

一棵子树的中序首结点是沿真实左孩子走到最左者；当前结点若有后继线索，直接沿线索走，否则去真实右子树的最左结点。

ThreadNode* firstInorder(ThreadNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    while (root->leftTag == PointerTag::Child
            && root->left != nullptr) {
        root = root->left;
    }
    return root;
}

ThreadNode* nextInorder(ThreadNode* node) {
    if (node == nullptr) {
        return nullptr;
    }
    if (node->rightTag == PointerTag::Thread) {
        return node->right;
    }
    return firstInorder(node->right);
}

std::vector<int> inorderThreaded(ThreadNode* root) {
    std::vector<int> order;
    for (ThreadNode* node = firstInorder(root);
         node != nullptr;
         node = nextInorder(node)) {
        order.push_back(node->data);
    }
    return order;
}

原稿把输出语句放到了遍历循环之外，循环结束时 q 已为空；GetFirst 也没有处理空树。

题 33：按先序序列建立二叉搜索树并先序遍历

源 PDF 本题答案区为空。若给定的是关键字互异的 BST 先序序列，按该次序逐个执行 BST 插入即可重建原树；重复关键字的处理必须事先约定，下列实现选择忽略重复值。

void insertBST(BTNode*& root, int key) {
    if (root == nullptr) {
        root = new BTNode{key, nullptr, nullptr};
    } else if (key < root->data) {
        insertBST(root->left, key);
    } else if (key > root->data) {
        insertBST(root->right, key);
    }
}

BTNode* buildBSTFromPreorder(const std::vector<int>& preorder) {
    BTNode* root = nullptr;
    for (int key : preorder) {
        insertBST(root, key);
    }
    return root;
}

建立后调用题 19 的 preorderIterative 即可得到先序遍历结果。普通逐项插入平均时间 $O(n\log n)$，输入已经单调时树会退化，最坏为 $O(n^2)$。

题 34：求中序线索二叉树结点的前驱

若 leftTag == Thread，左指针已直接指向中序前驱；
若左指针是真实左孩子，前驱就是左子树中沿真实右孩子走到的最右结点。

ThreadNode* inorderPredecessor(ThreadNode* node) {
    if (node == nullptr) {
        return nullptr;
    }
    if (node->leftTag == PointerTag::Thread) {
        return node->left;
    }

    ThreadNode* predecessor = node->left;
    while (predecessor != nullptr
            && predecessor->rightTag == PointerTag::Child
            && predecessor->right != nullptr) {
        predecessor = predecessor->right;
    }
    return predecessor;
}

原稿在 else 分支使用了未声明的 p，且没有先令它指向当前结点的真实左孩子。

题 35：孩子兄弟表示法统计一般树叶结点

孩子兄弟表示中，firstChild 指向第一个孩子，nextSibling 指向下一个兄弟。一般树叶结点的判据是“没有第一个孩子”，与是否有右兄弟无关。

struct ChildSiblingNode {
    int data{};
    ChildSiblingNode* firstChild = nullptr;
    ChildSiblingNode* nextSibling = nullptr;
};

std::size_t generalTreeLeafCount(
        const ChildSiblingNode* root) {
    if (root == nullptr) {
        return 0;
    }
    const std::size_t self =
        root->firstChild == nullptr ? 1 : 0;
    return self
         + generalTreeLeafCount(root->firstChild)
         + generalTreeLeafCount(root->nextSibling);
}

调用时传入整棵一般树的根（根没有兄弟）；若传入兄弟链中的一个结点，本函数还会一并统计其后续兄弟所在的树。原稿注释把叶结点条件说成“右孩子为空”，但代码实际检查的是左指针；函数体还混用了未声明的 p。正确知识点是：左指针为空才表示没有孩子。

8. 原稿关键纠错汇总

题号	原稿问题	本文处理
1、4、11、17	左右递归多次写成左子树	所有左右递归、右孩子赋值均已逐项校正
5、6	表达式分支与最值遍历控制流错误	明确叶/分支语义；最大值搜索无条件遍历两侧
9～11	结果按值传递或命中后不能全局停止	使用返回指针/层号，把成功状态逐层传播
12	只把指针置空，整棵后代泄漏	后序释放并把父链接置空
13、14	`head/tail` 按值传递；叶路径不回溯	引用传递；所有路径统一成对压入、弹出
15～17	区间公式、拼写、空位与左右赋值错误	明确完美树前提，重算区间并支持空位置
19～23	缺少访问、空指针解引用、祖先栈混用	使用标准单栈遍历、路径法和经过存在性检查的 LCA
25～29	队列元素类型、层号写入、计数、边界变量错误	用标准队列及每层长度统一处理
31、32、34	结点声明、标志、输出位置和前驱指针错误	用强类型标志，补全建立、遍历、前驱
33	原 PDF 答案为空	补全 BST 插入建树和先序复用方式
35	孩子兄弟树的叶判据注释错误	以 `firstChild == nullptr` 为准

9. 覆盖核对

原题号	已覆盖内容
1～4	结点总数、叶数、双分支数、深度
5～8	表达式求值、最大结点、结构相似、镜像
9～14	查找、第 $k$ 个先序结点、层号、删子树、叶链表、根叶路径
15～17	满二叉树序列转换、先序中序建树、顺序转链式
18	原文件无此题
19～23	三种非递归遍历、祖先、最近公共祖先
24～29	层序、逆向层序、宽度、层序树高、完全性、WPL
30	原文件无此题
31～35	中序线索化、线索遍历、BST 建树、线索前驱、孩子兄弟叶数

10. 本节复盘

计算型递归通常最稳：空树给单位结果，当前结点贡献与左右结果合并。
查找必须把“已经找到”的状态逐层返回；修改根指针、头尾指针时使用引用。
路径题的压入与弹出必须严格成对；删除题还必须释放整棵子树。
非递归后序的关键是区分“右子树尚未访问”和“右子树刚访问完”。
层次统计优先使用每轮的队列长度，它天然给出当前层边界。
完全二叉树在第一个空位置后不能再出现非空结点。
线索二叉树必须依标志区分孩子与线索，普通树递归不能直接用于已线索化结构。
孩子兄弟表示中，左指针代表第一个孩子、右指针代表兄弟；叶结点只看有没有孩子。