题目描述

恢复二叉搜索树

给定一个二叉搜索树（BST）的两个节点的值，这两个节点分别被错误地交换了位置，导致BST不再保持二叉搜索树的性质。请编写一个算法来恢复这个BST，要求只能使用恒定的额外空间（即 O(1) 额外空间）。

注意：

1. 树中的节点数量在范围 [2, 1000] 内。
2. 每个节点的值都是唯一的，且在范围 [1, 10^4] 内。

示例

假设给定的BST如下（用中序遍历表示，以便更容易看出问题）：

3
   \
    1
   /
  2

显然，1 和 2 被错误地交换了位置。恢复后的BST应为：

2
   \
    1
   /
  3

解题思路

为了找到被错误交换的节点并恢复BST，我们可以使用中序遍历（左-根-右）。在BST的中序遍历中，节点应该按照升序排列。因此，错误交换的两个节点将会是中序遍历中相邻但顺序相反的两个节点。

我们可以使用两个指针（prev 和 first）来跟踪中序遍历中的前一个节点和第一个顺序错误的节点。当遇到第一个顺序错误的节点时，我们还需要找到第二个顺序错误的节点（即 prev 在下一次迭代时的值）。然后，我们交换这两个节点的值。

示例代码

PHP

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function recoverTree($root) {
    $prev = null;
    $first = null;
    $second = null;
    inorder($root, $prev, $first, $second);
    
    // 交换两个节点的值
    $temp = $first->val;
    $first->val = $second->val;
    $second->val = $temp;
}

function inorder($node, &$prev, &$first, &$second) {
    if ($node === null) return;
    inorder($node->left, $prev, $first, $second);
    
    if ($prev !== null && $prev->val > $node->val) {
        if ($first === null) {
            $first = $prev;
        }
        $second = $node;
    }
    $prev = $node;
    
    inorder($node->right, $prev, $first, $second);
}

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root):
    prev, first, second = None, None, None
    def inorder(node):
        nonlocal prev, first, second
        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

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function recoverTree(root) {
    let prev = null, first = null, second = null;
    function 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);
    [first.val, second.val] = [second.val, first.val];
}

码小课网站中有更多相关内容分享给大家学习，包括数据结构与算法的各种知识，以及实战应用等。