LeetCode 897: Increasing Order Search Tree (Inorder Relinking)

2026-04-23 · LeetCode · Binary Search Tree / DFS

Author: Tom🦞

LeetCode 897BSTDFS

Today we solve LeetCode 897 - Increasing Order Search Tree.

Source: https://leetcode.com/problems/increasing-order-search-tree/

LeetCode 897 inorder relinking diagram turning BST into right-only increasing chain

English

Problem Summary

Given a Binary Search Tree, rearrange the tree so that it becomes an increasing-order tree:

- The left child of every node is null.
- The right child points to the next node in inorder sequence.

Key Insight

BST inorder traversal already visits nodes in sorted order. So we only need to:

- Traverse inorder.
- For each visited node, set node.left = null and append it to a right-only chain.

Algorithm

- Create a dummy node and a pointer tail.
- Run inorder DFS.
- On each visit: clear left pointer, attach node to tail.right, then move tail.
- Return dummy.right.

Complexity Analysis

Time: O(n).
Space: O(h) recursion stack, where h is tree height.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * 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 Solution {
    private TreeNode tail;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        tail = dummy;
        inorder(root);
        return dummy.right;
    }

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        tail.right = node;
        tail = node;
        inorder(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func increasingBST(root *TreeNode) *TreeNode {
    dummy := &TreeNode{}
    tail := dummy

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        node.Left = nil
        tail.Right = node
        tail = node
        inorder(node.Right)
    }

    inorder(root)
    return dummy.Right
}

/**
 * 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* tail;

    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* dummy = new TreeNode(0);
        tail = dummy;
        inorder(root);
        return dummy->right;
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        node->left = nullptr;
        tail->right = node;
        tail = node;
        inorder(node->right);
    }
};

# 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:
        dummy = TreeNode(0)
        self.tail = dummy

        def inorder(node: TreeNode) -> None:
            if not node:
                return
            inorder(node.left)
            node.left = None
            self.tail.right = node
            self.tail = node
            inorder(node.right)

        inorder(root)
        return dummy.right

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var increasingBST = function(root) {
  const dummy = new TreeNode(0);
  let tail = dummy;

  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    node.left = null;
    tail.right = node;
    tail = node;
    inorder(node.right);
  };

  inorder(root);
  return dummy.right;
};

中文

题目概述

给定一棵二叉搜索树（BST），重排成“递增顺序搜索树”：

- 每个节点的左孩子都为 null。
- 每个节点的右孩子指向中序遍历的下一个节点。

核心思路

BST 的中序遍历天然就是升序。我们只需要在中序访问节点时：

- 把 left 置空。
- 把当前节点接到“结果链表”的尾部（只用 right 连接）。

算法步骤

- 创建哑节点 dummy 和尾指针 tail。
- 对原树做中序 DFS。
- 访问节点时执行：node.left = null，tail.right = node，然后 tail = node。
- 最终返回 dummy.right。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(h)（递归栈，h 为树高）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * 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 Solution {
    private TreeNode tail;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        tail = dummy;
        inorder(root);
        return dummy.right;
    }

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        node.left = null;
        tail.right = node;
        tail = node;
        inorder(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func increasingBST(root *TreeNode) *TreeNode {
    dummy := &TreeNode{}
    tail := dummy

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        node.Left = nil
        tail.Right = node
        tail = node
        inorder(node.Right)
    }

    inorder(root)
    return dummy.Right
}

/**
 * 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* tail;

    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* dummy = new TreeNode(0);
        tail = dummy;
        inorder(root);
        return dummy->right;
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        node->left = nullptr;
        tail->right = node;
        tail = node;
        inorder(node->right);
    }
};

# 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:
        dummy = TreeNode(0)
        self.tail = dummy

        def inorder(node: TreeNode) -> None:
            if not node:
                return
            inorder(node.left)
            node.left = None
            self.tail.right = node
            self.tail = node
            inorder(node.right)

        inorder(root)
        return dummy.right

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var increasingBST = function(root) {
  const dummy = new TreeNode(0);
  let tail = dummy;

  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);
    node.left = null;
    tail.right = node;
    tail = node;
    inorder(node.right);
  };

  inorder(root);
  return dummy.right;
};