13.5 二叉查找树

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树：对于每个父节点，其左子树中所有节点的值小于等于父结点的值，其右子树中所有节点的值大于等于父结点的值。因此对于一个二叉查找树，我们可以在 O(log n) 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组。

例如下面这棵树即为二叉查找树，其中序遍历结果为 [1 2 3 4 5 6]。

    4
   / \
  2   5
 / \   \
1   3   6

99. Recover Binary Search Tree

题目描述

给定一个二叉查找树，已知有两个节点被不小心交换了，试复原此树。

输入输出样例

输入是一个被误交换两个节点的二叉查找树，输出是改正后的二叉查找树。

Input:
  3
 / \
1   4
   /
  2
Output:
  2
 / \
1   4
   /
  3

在这个样例中，2 和 3 被不小心交换了。

题解

我们可以使用中序遍历这个二叉查找树，同时设置一个 prev 指针，记录当前节点中序遍历时的前节点。如果当前节点大于 prev 节点的值，说明需要调整次序。有一个技巧是如果遍历整个序列过程中只出现了一次次序错误，说明就是这两个相邻节点需要被交换；如果出现了两次次序错误，那就需要交换这两个节点。

C++

// 辅函数。
void inorder(TreeNode* root, TreeNode*& mistake1, TreeNode*& mistake2,
             TreeNode*& prev) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left, mistake1, mistake2, prev);
    if (prev != nullptr && root->val < prev->val) {
        if (mistake1 == nullptr) {
            mistake1 = prev;
        }
        mistake2 = root;
    }
    prev = root;
    inorder(root->right, mistake1, mistake2, prev);
}
// 主函数。
void recoverTree(TreeNode* root) {
    TreeNode *mistake1 = nullptr, *mistake2 = nullptr, *prev = nullptr;
    inorder(root, mistake1, mistake2, prev);
    if (mistake1 != nullptr && mistake2 != nullptr) {
        swap(mistake1->val, mistake2->val);
    }
}

Python

# 辅函数。
# 注意，Python中并不方便在辅函数中直接传指针，因此我们建造长度为1的list进行传引用。
def inorder(
    root: Optional[TreeNode],
    mistake1=List[Optional[TreeNode]],
    mistake2=List[Optional[TreeNode]],
    prev=List[Optional[TreeNode]],
):
    if root is None:
        return
    inorder(root.left, mistake1, mistake2, prev)
    if prev[0] is not None and root.val < prev[0].val:
        if mistake1[0] is None:
            mistake1[0] = prev[0]
        mistake2[0] = root
    prev[0] = root
    inorder(root.right, mistake1, mistake2, prev)

# 主函数。
def recoverTree(root: Optional[TreeNode]) -> None:
    mistake1, mistake2, prev = [None], [None], [None]
    inorder(root, mistake1, mistake2, prev)
    if mistake1[0] is not None and mistake2[0] is not None:
        mistake1[0].val, mistake2[0].val = mistake2[0].val, mistake1[0].val

669. Trim a Binary Search Tree

题目描述

给定一个二叉查找树和两个整数 L 和 R，且 L < R，试修剪此二叉查找树，使得修剪后所有节点的值都在 [L, R] 的范围内。

输入输出样例

输入是一个二叉查找树和两个整数 L 和 R，输出一个被修剪好的二叉查找树。

Input: L = 1, R = 3, tree =
      3
     / \
    0   4
     \
      2
     /
    1
Output:
    3
   /
  2
 /
1

题解

利用二叉查找树的大小关系，我们可以很容易地利用递归进行树的处理。

C++

TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (root == nullptr) {
        return root;
    }
    if (root->val > high) {
        return trimBST(root->left, low, high);
    }
    if (root->val < low) {
        return trimBST(root->right, low, high);
    }
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

Python

def trimBST(
    root: Optional[TreeNode], low: int, high: int
) -> Optional[TreeNode]:
    if root is None:
        return None
    if root.val > high:
        return trimBST(root.left, low, high)
    if root.val < low:
        return trimBST(root.right, low, high)
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root