What is the main goal of the Increasing Order Search Tree problem?

The goal is to transform a BST into a right-skewed tree where all nodes are in ascending order and each node has no left child.

Can this problem be solved iteratively?

Yes, you can use an explicit stack to perform in-order traversal iteratively and link nodes in increasing order.

Why do we need a dummy node in some solutions?

A dummy node simplifies reconnection logic, allowing easy attachment of the first real node without special head handling.

What common mistakes should I avoid when solving this problem?

Ensure left children are set to null, maintain the previous node pointer for linking, and reconstruct nodes rather than just creating an array.

Does this problem require preserving the original BST structure?

No, the original tree structure changes; only the node values and in-order sequence are preserved, resulting in a right-skewed tree.

#897

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

递增顺序搜索树

给你一棵二叉搜索树的 root ，请你按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。示例 1：输入： root = [5,3,6,2,4,null,8,1,null,null,null,7,9] 输出： [1,nul…

栈树深度优先搜索二叉搜索树二叉树

题目描述

给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

lightbulb

解题思路

方法一：DFS 中序遍历

我们定义一个虚拟节点 $dummy$ ，初始时 $dummy$ 的右子节点指向根节点 $root$ ，定义一个指针 $prev$ 指向 $dummy$ 。

我们对二叉搜索树进行中序遍历，遍历过程中，每遍历到一个节点，就将 $prev$ 的右子节点指向它，然后将当前节点的左子节点置为空，再将当前节点赋值给 $prev$ ，以便于下一次遍历。

遍历结束后，原二叉搜索树被修改成只有右子节点的单链表，我们再将虚拟节点 $dummy$ 的右子节点返回即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉搜索树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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.right

speed

复杂度分析

指标	值
时间	complexity is O(n) because every node is visited exactly once during traversal. Space complexity is O(h) for recursion stack or O(n) for iterative stack in the worst case, where h is the tree height and n is the number of nodes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking for correct in-order traversal and reconnection of nodes
question_mark
Looking for proper nullification of left children to maintain right-skewed structure
question_mark
Expecting handling of both recursive and iterative DFS approaches for clarity and efficiency

warning

常见陷阱

外企场景

error
Forgetting to set left children to null, causing cycles or incorrect tree shape
error
Not maintaining a previous node reference, which breaks the increasing sequence linkage
error
Assuming a new array output rather than reconstructing the tree nodes, which is inefficient

swap_horiz

进阶变体

外企场景

arrow_right_alt
Create a decreasing order search tree by reversing in-order traversal
arrow_right_alt
Flatten the BST to a linked list in-place with both left and right pointers set to null or used for next node
arrow_right_alt
Apply the same in-order reconstruction approach to a general binary tree, not strictly a BST

help

常见问题

外企场景

继续练习

#938 二叉搜索树的范围和 #1008 前序遍历构造二叉搜索树 #783 二叉搜索树节点最小距离