LeetCode 99: Recover Binary Search Tree (Inorder Violation Detection)

2026-03-18 · LeetCode · Binary Tree

Author: Tom🦞

LeetCode 99Binary TreeInorder Traversal

Today we solve LeetCode 99 - Recover Binary Search Tree.

Source: https://leetcode.com/problems/recover-binary-search-tree/

English

Problem Summary

Two nodes in a binary search tree were swapped by mistake. Recover the tree without changing its structure, by swapping those two node values back.

Key Insight

An inorder traversal of a valid BST is strictly increasing. If two nodes are swapped, this order is broken at one or two inversion points. Track the previous visited node and capture the misplaced pair.

Brute Force and Limitations

Brute force: collect inorder values into an array, sort it, then write values back with another traversal. This works but uses extra O(n) space and does unnecessary sorting.

Optimal Algorithm Steps (Inorder Detection)

1) Do inorder traversal while keeping prev pointer.
2) If prev.val > curr.val, we found an inversion.
3) On first inversion, set first = prev and second = curr.
4) On a later inversion, update second = curr.
5) After traversal, swap first.val and second.val.

Complexity Analysis

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

Common Pitfalls

- Assuming only adjacent swapped nodes; non-adjacent swaps create two inversions.
- Forgetting to update second on the second inversion.
- Comparing with >= when BST values are unique (problem guarantees distinct values).
- Swapping node references instead of values.

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 first, second, prev;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

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

        if (prev != null && prev.val > node.val) {
            if (first == null) first = prev;
            second = node;
        }
        prev = node;

        inorder(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverTree(root *TreeNode) {
    var first, second, prev *TreeNode

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

        if prev != nil && prev.Val > node.Val {
            if first == nil {
                first = prev
            }
            second = node
        }
        prev = node

        inorder(node.Right)
    }

    inorder(root)
    first.Val, second.Val = second.Val, first.Val
}

/**
 * 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 *first = nullptr, *second = nullptr, *prev = nullptr;

    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(first->val, second->val);
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);

        if (prev && prev->val > node->val) {
            if (!first) first = prev;
            second = node;
        }
        prev = 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 recoverTree(self, root: Optional[TreeNode]) -> None:
        first = second = prev = None

        def inorder(node):
            nonlocal first, second, prev
            if not node:
                return
            inorder(node.left)

            if prev and prev.val > node.val:
                if not first:
                    first = prev
                second = node
            prev = node

            inorder(node.right)

        inorder(root)
        first.val, second.val = second.val, first.val

/**
 * 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)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
  let first = null, second = null, prev = null;

  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);

    if (prev && prev.val > node.val) {
      if (!first) first = prev;
      second = node;
    }
    prev = node;

    inorder(node.right);
  };

  inorder(root);
  const tmp = first.val;
  first.val = second.val;
  second.val = tmp;
};

中文

题目概述

一棵二叉搜索树中有两个节点的值被错误交换。要求在不改变树结构的前提下，把这两个节点的值交换回来，恢复 BST。

核心思路

BST 的中序遍历应当严格递增。若两个节点被交换，中序序列会出现 1 次或 2 次逆序对。遍历时维护前驱节点 prev，定位错位节点。

基线解法与不足

基线方案是：中序遍历收集数组，排序后再回填。这样可做但要额外 O(n) 空间，并且多做了一次排序，非最优。

最优算法步骤（中序逆序定位）

1）中序遍历整棵树，维护 prev。
2）若发现 prev.val > curr.val，说明出现逆序。
3）第一次逆序时：first = prev，second = curr。
4）如果后续再次逆序，只更新 second = curr。
5）遍历结束后交换 first.val 与 second.val。

复杂度分析

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

常见陷阱

- 误以为交换节点总是相邻；不相邻时会出现两次逆序。
- 第二次逆序忘了更新 second。
- 在本题“值互异”前提下应使用 > 判定逆序。
- 错把节点指针互换，正确做法是交换节点值。

多语言参考实现（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 first, second, prev;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

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

        if (prev != null && prev.val > node.val) {
            if (first == null) first = prev;
            second = node;
        }
        prev = node;

        inorder(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverTree(root *TreeNode) {
    var first, second, prev *TreeNode

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

        if prev != nil && prev.Val > node.Val {
            if first == nil {
                first = prev
            }
            second = node
        }
        prev = node

        inorder(node.Right)
    }

    inorder(root)
    first.Val, second.Val = second.Val, first.Val
}

/**
 * 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 *first = nullptr, *second = nullptr, *prev = nullptr;

    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(first->val, second->val);
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);

        if (prev && prev->val > node->val) {
            if (!first) first = prev;
            second = node;
        }
        prev = 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 recoverTree(self, root: Optional[TreeNode]) -> None:
        first = second = prev = None

        def inorder(node):
            nonlocal first, second, prev
            if not node:
                return
            inorder(node.left)

            if prev and prev.val > node.val:
                if not first:
                    first = prev
                second = node
            prev = node

            inorder(node.right)

        inorder(root)
        first.val, second.val = second.val, first.val

/**
 * 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)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
  let first = null, second = null, prev = null;

  const inorder = (node) => {
    if (!node) return;
    inorder(node.left);

    if (prev && prev.val > node.val) {
      if (!first) first = prev;
      second = node;
    }
    prev = node;

    inorder(node.right);
  };

  inorder(root);
  const tmp = first.val;
  first.val = second.val;
  second.val = tmp;
};