LeetCode 897简单树 · BST
递增顺序搜索树 图解题解
这道题到底在问什么
给定二叉搜索树 root，按中序遍历把它重排成一棵递增顺序搜索树：树中最小的节点成为根，之后每个节点都只有右孩子、没有左孩子，整体是一条从小到大的右斜链。
- 输入
- root=[50,30,80,20,40,70,90]
- 输出
- 20→30→40→50→70→80→90（只有右孩子的单链）
最优解：一步一步想明白
- 3记牢这套「中序天然升序、逐个接到 prev 右边、清空左指针、prev 前移」，下面每一帧都在套它。
- 4prev = 虚拟头开局先造一个虚拟头结点，让 prev 指向它，递归栈和藤蔓链都还是空的。接下来从根节点 50 出发，按「左、根、右」的中序顺序走，一路先往最左下钻。
- 5压入 50中序要「先把左边走完」，所以把 50 压进递归栈，再往它的左孩子 30 继续下探。栈里现在等着 50。
- 6压入 30中序要「先把左边走完」，所以把 30 压进递归栈，再往它的左孩子 20 继续下探。栈里现在等着 50、30。
- 7压入 20中序要「先把左边走完」，所以把 20 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 20 真正访问掉。
- 8访问 20左边已经走干净，弹出栈顶 20，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 20 是眼下藤蔓链该接的下一个值。
- 9虚拟头 → 20把 20 接到上一个节点（prev = 虚拟头）的右指针后面，同时把 20 自己的左指针清空，让它在新链里只剩右孩子。20 标绿，表示已经进了藤蔓链：20。然后 prev 前移到 20，20 没有右子树，回头继续弹栈。
- 10访问 30左边已经走干净，弹出栈顶 30，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 30 是眼下藤蔓链该接的下一个值。
- 1120 → 30把 30 接到上一个节点（prev = 20）的右指针后面，同时把 30 自己的左指针清空，让它在新链里只剩右孩子。30 标绿，表示已经进了藤蔓链：20 → 30。然后 prev 前移到 30，接着去处理 30 的右子树（从 40 开始）。
- 12压入 40中序要「先把左边走完」，所以把 40 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 40 真正访问掉。
- 13访问 40左边已经走干净，弹出栈顶 40，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 40 是眼下藤蔓链该接的下一个值。
- 1430 → 40把 40 接到上一个节点（prev = 30）的右指针后面，同时把 40 自己的左指针清空，让它在新链里只剩右孩子。40 标绿，表示已经进了藤蔓链：20 → 30 → 40。然后 prev 前移到 40，40 没有右子树，回头继续弹栈。
- 15访问 50左边已经走干净，弹出栈顶 50，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 50 是眼下藤蔓链该接的下一个值。
- 1640 → 50把 50 接到上一个节点（prev = 40）的右指针后面，同时把 50 自己的左指针清空，让它在新链里只剩右孩子。50 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50。然后 prev 前移到 50，接着去处理 50 的右子树（从 80 开始）。
- 17压入 80中序要「先把左边走完」，所以把 80 压进递归栈，再往它的左孩子 70 继续下探。栈里现在等着 80。
- 18压入 70中序要「先把左边走完」，所以把 70 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 70 真正访问掉。
- 19访问 70左边已经走干净，弹出栈顶 70，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 70 是眼下藤蔓链该接的下一个值。
- 2050 → 70把 70 接到上一个节点（prev = 50）的右指针后面，同时把 70 自己的左指针清空，让它在新链里只剩右孩子。70 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50 → 70。然后 prev 前移到 70，70 没有右子树，回头继续弹栈。
- 21访问 80左边已经走干净，弹出栈顶 80，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 80 是眼下藤蔓链该接的下一个值。
- 2270 → 80把 80 接到上一个节点（prev = 70）的右指针后面，同时把 80 自己的左指针清空，让它在新链里只剩右孩子。80 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50 → 70 → 80。然后 prev 前移到 80，接着去处理 80 的右子树（从 90 开始）。
- 23压入 90中序要「先把左边走完」，所以把 90 压进递归栈，它已经没有左孩子了，左边到底，下一步该回头把栈顶的 90 真正访问掉。
- 24访问 90左边已经走干净，弹出栈顶 90，这就是当前中序序列里轮到的节点（高亮）。它前面比它小的节点都处理完了，所以 90 是眼下藤蔓链该接的下一个值。
- 2580 → 90把 90 接到上一个节点（prev = 80）的右指针后面，同时把 90 自己的左指针清空，让它在新链里只剩右孩子。90 标绿，表示已经进了藤蔓链：20 → 30 → 40 → 50 → 70 → 80 → 90。然后 prev 前移到 90，90 没有右子树，回头继续弹栈。
- 26新根 = 20中序走完，七个节点按 20、30、40、50、70、80、90 的升序依次接成了一条右斜链。最左下的 20 成了新根，每个节点都只有右孩子。返回虚拟头的右孩子 20，整道题就解完了。
⚠️ 容易写错的地方
✗ 错：只做 prev.right = root，忘了 root.left = null
✓ 对：两步都要做
不清空左指针，新链里会残留原来的左子树，结果既不是单链、还可能成环
✗ 错：接线后忘了 prev = root 前移
✓ 对：每接一个就把 prev 移到它
prev 不前移，所有节点都会被接到同一个节点右边，互相覆盖
✗ 错：不用虚拟头，特判第一个节点
✓ 对：用 dummy 让 prev 起步有落点
没有 dummy 就要为「第一个被访问的节点」单独写分支，容易漏；最后返回 dummy.right 即可
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
def dfs(root):
if root is None:
return
nonlocal prev
dfs(root.left)
prev.right = root
root.left = None
prev = root
dfs(root.right)
dummy = prev = TreeNode(right=root)
dfs(root)
return dummy.rightC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode* dummy = new TreeNode(0, nullptr, root);
TreeNode* prev = dummy;
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
if (!root) {
return;
}
dfs(root->left);
prev->right = root;
root->left = nullptr;
prev = root;
dfs(root->right);
};
dfs(root);
return dummy->right;
}
};Java
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private TreeNode prev;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummy = new TreeNode(0, null, root);
prev = dummy;
dfs(root);
return dummy.right;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
prev.right = root;
root.left = null;
prev = root;
dfs(root.right);
}
}复杂度
时间
O(n)
中序遍历把每个节点恰好访问一次，接线是常数操作
空间
O(h)
递归栈深 = 树高 h；平衡时 O(log n)，退化成链时最坏 O(n)。不新建结果链里的业务节点，只额外用一个 dummy 哨兵结点，原地改指针
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 递增顺序搜索树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么要引入虚拟头结点 dummy？不能直接用第一个节点吗？+
可以，但要多写特判。第一个被中序访问到的节点是新链的头，如果不用 dummy，就得专门判断「现在是不是第一个节点」来决定是设新根还是接 prev.right。引入 dummy 后，prev 一开始就有落点，第一个节点直接接到 dummy.right，逻辑统一，最后返回 dummy.right 即可，省掉边界分支。
除了递归，还有别的中序遍历写法吗？空间能不能更省？+
可以用显式栈做迭代中序，效果一样、空间还是 O(h)；想把空间压到 O(1)，可以用 Morris 中序遍历，借助叶子的空右指针做线索、遍历完再拆掉，不用递归栈也不用显式栈。本题用递归最直观，Morris 是进阶优化，面试讲清思路即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 递增顺序搜索树 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。