面试题36：二叉搜索树与双向链表

从“链表首尾需要闭环吗”开始

先预测：转换后最小节点4的left应该指向最大节点16吗？作者答案是不。题目要求排序双向链表，源码打印时从头沿right走到nullptr，再从尾沿left走回nullptr；结果是线性链，不是循环链。

“二叉搜索树与双向链表”转换不创建新节点，只调整原节点指针。left从左孩子改为前驱，right从右孩子改为后继。结果是升序双向链表；完成后树结构不再存在。

旧页把head.left连到tail、tail.right连到head，改变了作者契约，也会让按nullptr终止的PrintDoubleLinkedList无限循环。本章严格保留线性边界。

中序遍历给出升序邻接

二叉搜索树满足左子树值小于当前、右子树值大于当前，因此按非递减或严格递增顺序访问节点，具体取决于重复键政策。

若已按中序处理到当前节点，刚刚访问的节点就是当前。只需令current.left指向前驱，并令前驱.right指向current，就完成一对双向链接。

“当前节点与前一节点互连”不需要提前知道后继：当前节点先成为尾；以后访问下一个节点时，它会反过来把当前作为前驱，顺便补上当前.right。

已转换前缀与尾指针不变量

作者把pLastNodeInList通过二级指针传入递归。每次调用完成后，调用者都能看到更新后的链尾，而不是只修改局部指针副本。

进入当前节点前先“递归转换左右子树”中的左子树部分；左递归完成后，last是左侧已转换链最大节点。连接当前、更新last，再递归右子树。右递归会继续把其最小节点接到当前后面。

把从最小值到last的链称为。每访问一个节点，前缀只在尾部追加，不会重新搜索链表。

忠实还原作者尾指针递归

ConvertNode空节点直接返回。Convert创建last为空，递归结束后last指向最大节点，也就是链尾；作者再沿left一直走到最小节点，得到链头。

struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
 
void ConvertNode(BinaryTreeNode* pNode,
                 BinaryTreeNode** pLastNodeInList) {
    if (pNode == nullptr) {
        return;
    }
 
    BinaryTreeNode* pCurrent = pNode;
    if (pCurrent->m_pLeft != nullptr) {
        ConvertNode(
            pCurrent->m_pLeft, pLastNodeInList);
    }
 
    pCurrent->m_pLeft = *pLastNodeInList;
    if (*pLastNodeInList != nullptr) {
        (*pLastNodeInList)->m_pRight = pCurrent;
    }
    *pLastNodeInList = pCurrent;
 
    if (pCurrent->m_pRight != nullptr) {
        ConvertNode(
            pCurrent->m_pRight, pLastNodeInList);
    }
}
 
BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree) {
    BinaryTreeNode* pLastNodeInList = nullptr;
    ConvertNode(pRootOfTree, &pLastNodeInList);
 
    BinaryTreeNode* pHeadOfList = pLastNodeInList;
    while (pHeadOfList != nullptr &&
           pHeadOfList->m_pLeft != nullptr) {
        pHeadOfList = pHeadOfList->m_pLeft;
    }
    return pHeadOfList;
}

第一次访问最小节点时last为空，因此其left被设为空，形成头边界。最大节点原本没有右子树；它成为最终last后right仍为空，形成尾边界。作者没有额外写边界，就是利用BST极值节点的空孩子。

修改right前为何不会丢失右子树

连接当前节点时只写current.left和last.right。last是中序前驱，已经完成其原右子树的递归；把last.right改为current正是把前驱后继相连。

current.right在递归右子树之前仍保留原右孩子。直到右子树最小节点被处理时，算法才通过“前驱.right=当前”把current.right更新为链表后继。因此访问所需树边在使用前没有被破坏。

若先把current.right改成后继占位再递归，会丢失原右子树入口；若当前节点在左递归前就改left，也会丢失原左子树。修改时机必须位于左右递归之间，也就是中序“访问当前”位置。

原地转换与所有权语义

节省节点分配，但具有破坏性。调用后原root可能位于链中间，不再是树根；对它递归DestroyTree会沿前驱后继形成反向边，可能重复释放或无限递归。作者改用DestroyList从head沿right逐个删除。

函数不能安全地对同一结构调用两次。第二次输入已是双向链，left/right形成相邻双向关系，递归会沿left回走并成环。类型系统若仍把结果标成BinaryTreeNode，调用方更要靠文档区分当前状态。

更稳健的API可返回拥有head的DoublyLinkedList类型，并把输入所有权显式移动进去；若业务还需要原树，应先深拷贝或创建新链节点，不能选择原地题解后期待树仍可读。

显式栈迭代版

极深偏斜树可能导致递归栈溢出。迭代中序用显式stack保存尚未访问的祖先，访问节点时执行同一前驱链接。它可直接记录首个节点为head，省去从tail沿left再走一遍。

#include <stack>
#include <utility>
 
struct TreeNode {
    int value;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};
 
std::pair<TreeNode*, TreeNode*> convertIterative(
    TreeNode* root) {
    std::stack<TreeNode*> pending;
    TreeNode* current = root;
    TreeNode* head = nullptr;
    TreeNode* last = nullptr;
 
    while (current != nullptr || !pending.empty()) {
        while (current != nullptr) {
            pending.push(current);
            current = current->left;
        }
 
        current = pending.top();
        pending.pop();
        TreeNode* originalRight = current->right;
 
        current->left = last;
        if (last != nullptr) {
            last->right = current;
        } else {
            head = current;
        }
        last = current;
        current = originalRight;
    }
 
    if (last != nullptr) last->right = nullptr;
    return {head, last};
}

保存originalRight非常关键：链接前驱时可能不会改current.right，但明确保存使后续重构不易误删原右入口。返回head和tail便于正反向验证；作者接口只返回head。

迭代辅助空间O(h)，与递归调用栈同阶，并没有变成O(1)。若要求真正常数辅助空间，可研究Morris中序线索化，但与原地双向改写叠加后证明和恢复更复杂，不属于作者方案。

作者五组测试怎样验双向性

Test1完整BST转换后正向4、6、8、10、12、14、16，反向16、14、12、10、8、6、4。打印函数先沿right找到尾，再从同一尾沿left返回，能同时检查两种方向。

Test2全左链5到1，链头是原最深节点1，正向1到5；Test3全右链1到5，原根就是head。两者锁定只有前驱或只有后继时的边界。Test4单节点1，left/right都为空；Test5空树返回nullptr。源码总计五组。

#include <cassert>
#include <vector>
 
void assertLinearList(TreeNode* head,
                      const std::vector<int>& expected) {
    std::vector<int> forward;
    TreeNode* tail = nullptr;
    for (TreeNode* p = head; p != nullptr; p = p->right) {
        if (p->right != nullptr) {
            assert(p->right->left == p);
        }
        forward.push_back(p->value);
        tail = p;
    }
    assert(forward == expected);
    assert(head == nullptr || head->left == nullptr);
    assert(tail == nullptr || tail->right == nullptr);
 
    std::vector<int> backward;
    for (TreeNode* p = tail; p != nullptr; p = p->left) {
        backward.push_back(p->value);
    }
    assert(backward ==
           std::vector<int>(expected.rbegin(), expected.rend()));
}

测试还要保存转换前节点地址集合，转换后正向遍历得到的地址集合必须完全相同，证明没有新建、丢失或重复节点。只比较值在重复键存在时无法发现节点遗漏。

复杂度与重复键

ConvertNode每个节点访问一次O(n)，最后从tail沿left找head再走至多n步，总时间仍O(n)。递归辅助空间O(h)，不创建输出节点；链表本身复用原n个节点。

若BST允许重复键，中序结果按树的重复策略非递减，转换仍保持该次序。题目“有序”不一定意味着严格递增；测试应按节点身份和非递减值检查。比较器不是Convert需要的输入，因为它信任原树已经满足BST约束。

非BST输入仍会按中序转成双向链，但值未必有序。函数不验证BST；若输入不可信，应在转换前只读校验，转换后已失去树结构，无法方便地追溯违反位置。

正确性证明

递归不变量是：处理当前中序位置前，last指向已转换前缀尾，该前缀从最小已访问节点到last双向连接正确；未访问子树仍保留必要树边。

左递归完成后last是左子树最大节点，即当前中序前驱。设置current.left=last与last.right=current，把当前追加到前缀；更新last后再递归右子树，右侧节点依次追加。空左子树和空右子树自然跳过。

首次追加时last为空，使head边界left为空；最终last是全树最大节点且right为空。所有节点由中序恰访问一次，故链包含全部原节点、顺序有序、相邻双向指针互逆。

并发与失败边界

转换期间树处于部分节点已是链、部分仍是树的混合状态，任何并发读者都无法按单一结构解释。必须独占写锁或转移唯一所有权。原地指针赋值本身不分配，正常实现不会因内存不足中途抛出，但访问非法树指针仍是未定义行为。

若需要取消操作，作者方案没有事务回滚；停止在中途会留下混合结构。应在开始前完成权限与取消检查，或使用新建节点的非破坏式转换后原子发布结果。

本章练习

概念说明

本章核心概念包括：中序遍历。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. BST中序遍历给出有序节点次序。
2. 当前节点与中序前一节点互连即可逐步构造双向链。
3. 作者通过二级指针让递归层共享并更新链尾last。
4. 左递归后连接当前，再递归右子树，不能提前覆盖孩子入口。
5. 最终last是尾，作者沿left回到头；结果是线性而非循环链表。
6. 转换原地复用left/right，完成后原树已被破坏。
7. 时间O(n)、递归或显式栈空间O(h)，不创建新节点。
8. 五组官方测试正反向验证完整树、左右链、单点与空树。

名词解释