当前位置: 面试刷题>> 恢复二叉搜索树 (经典算法题500道)


题目描述

恢复二叉搜索树

给定一个二叉搜索树(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];
}

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

推荐面试题