13.5 二叉查找树

# 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](https://leetcode.com/problems/recover-binary-search-tree/)

### 题目描述

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

### 输入输出样例

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

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

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

### 题解

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

```py
class Solution:
    def inorder(self, root, mistake1, mistake2, prev):
        if not root:
            return
        self.inorder(root.left, mistake1, mistake2, prev)
        if prev[0] and root.val < prev[0].val:
            if not mistake1[0]:
                mistake1[0] = prev[0]
            mistake2[0] = root
        prev[0] = root
        self.inorder(root.right, mistake1, mistake2, prev)

def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        mistake1, mistake2, prev = [None], [None], [None]
        self.inorder(root, mistake1, mistake2, prev)
        if mistake1[0] and mistake2[0]:
            mistake1[0].val, mistake2[0].val = mistake2[0].val, mistake1[0].val
```

## [669. Trim a Binary Search Tree](https://leetcode.com/problems/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
```

### 题解

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

```py
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)
        if root.val > high:
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root
```