BM30　二叉搜索树与双向链表¶

中等通过率 32.27%python3核心代码模式样例通过牛客 AC分治

牛客原题　源码

讲解章节：树的基础与遍历

一句话

中序遍历天然有序，遍历时顺手把前驱后继指针接上。

解题思路¶

这题考什么¶

BST（二叉搜索树，左子树全部小于根、右子树全部大于根）的中序遍历就是升序序列，而题目要的双向链表恰好也是升序。两件事的顺序完全相同，所以整题归约成一句话：按中序访问节点，把相邻的两个接起来。

接法由题面规定：复用 TreeNode 已有的两个字段，left 当前驱指针、 right 当后继指针，不新建任何节点。做法是在迭代中序里多维护一个 prev 表示「上一个被访问的节点」：

prev 为空说明当前节点是中序第一个，也就是最小值，记成链表头 head；
否则 prev.right = cur、cur.left = prev，把两个方向都接上。

然后 prev = cur，继续中序。

示例 1 的 {10,6,14,4,8,12,16}，中序是 4, 6, 8, 10, 12, 14, 16，
依次接成 4 <-> 6 <-> 8 <-> 10 <-> 12 <-> 14 <-> 16，返回 4。

数据规模与复杂度¶

0 <= n <= 1000，节点值满足 0 <= val <= 1000；时限「其他语言 2 秒」。中序遍历一趟，每个节点入栈出栈各一次，时间 O(n)；额外空间只有那个显式栈，O(h)，h 为树高，链状树退化到 O(n)。没有新建任何节点，符合题面「在原树上操作」的要求。

坑在哪¶

改指针之前必须先把 cur.right 存下来。这是本题最容易写错的一处：一旦执行 prev.right = cur，prev 原来的右子树就再也找不回来了；同理，弹出 cur、接完指针之后 cur.right 已经可能被下一步覆盖，所以中序的「转向右子树」必须用事先保存的 nxt，而不是现读 cur.right。
返回值不是一棵树，判题也不按树比。这题由 driver.py 驱动：驱动器拿到返回的 head 之后，先沿 right 正向走一遍收值，再找到尾节点沿 left 反向走一遍收值，拼成一整句话 From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4; 再和期望文本比。meta.json 的 judge 给它配的模式是 raw（不做方言解析、按原始文本比），因为这句话没有引号，按牛客方言解析会被顶层逗号切成列表，永远比不上。通用的树编码器在这里也用不了：它沿 left/right 做层序 BFS，而转换后的节点互相指回去，队列会无限膨胀直接跑到超时。
由第 2 条推出的实战后果：两个方向都必须接对。只写 prev.right = cur 而漏掉 cur.left = prev，正向那半句仍然正确，反向那半句会立刻露馅—— 驱动器就是为了抓这种错法才两个方向都走。
链表头的 left 与链表尾的 right 都必须保持 None。这份写法天然满足：中序第一个节点没有左孩子、最后一个节点没有右孩子，代码不会去动它们。若额外接成环，驱动器的保险丝会截断遍历，答案自然对不上。
空树返回 None，驱动器对应输出两个空列表的那句话。
n 可以取到 1000，而 CPython 的默认递归上限正是 1000 层：示例 2 的 {5,4,#,3,#,2,#,1} 已经是一条纯左斜链，真数据里同样形状放大到 1000 个节点就会 RecursionError，所以中序写成显式栈。

参考实现¶

solutions/nowcoder/BM30/sol.py
from typing import List, Optional


class Solution:
    def Convert(self, pRootOfTree: "Optional[TreeNode]") -> "Optional[TreeNode]":
        # 空树没有链表头，驱动器会输出两个空序列
        if pRootOfTree is None:
            return None
        head: "Optional[TreeNode]" = None   # 链表头 = 中序第一个 = 最小值
        prev: "Optional[TreeNode]" = None   # 上一个被访问的节点
        stack: List["TreeNode"] = []
        cur = pRootOfTree
        # 标准迭代中序：一路向左压栈 -> 弹出访问 -> 转向右子树
        while stack or cur is not None:
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            nxt = cur.right                 # 先存好右子树，下面要覆盖指针
            # 中序相邻的两个节点就是链表里相邻的两个，前后指针一起接
            if prev is None:
                head = cur                  # 中序的第一个节点就是链表头
            else:
                prev.right = cur            # 前驱 -> 后继
                cur.left = prev             # 后继 -> 前驱
            prev = cur
            cur = nxt                       # 用存下来的右子树继续中序
        return head

BM30 二叉搜索树与双向链表¶