BST.

98. 验证二叉搜索树

BST的性质与二叉树中序遍历完美契合，遍历完直接就是有序数组。

def isValidBST(self, root: TreeNode) -> bool:
    prev = -inf
    def inorder(root):
        nonlocal prev
        if not root:
            return True
        if not inorder(root.left):
            return False
        if root.val <= prev:
            return False
        prev = root.val
        return inorder(root.right)
    return inorder(root)

这里要检查的invariant是：中序遍历后一元素永远比前一元素大。

再来一个迭代版。书读百遍，其义自见。

def isValidBST(self, root: TreeNode) -> bool:
    if not root: return True
    stack = []
    cur = root
    prev = -inf
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            if cur.val <= prev:
                return False
            prev = cur.val
            cur = cur.right
    return True

530. 二叉搜索树的最小绝对差

根据BST性质，这就是拿root和leftRightmost/rightLeftmost比。

def getMinimumDifference(self, root: TreeNode) -> int:
    best = inf
    def minDiffStartingFrom(root):
        if not root:
            return inf
        leftRightmost = root.left if root.left else None
        while leftRightmost and leftRightmost.right:
            leftRightmost = leftRightmost.right
        rightLeftmost = root.right if root.right else None
        while rightLeftmost and rightLeftmost.left:
            rightLeftmost = rightLeftmost.left 
        return min(abs(root.val - leftRightmost.val) if leftRightmost else inf, abs(root.val-rightLeftmost.val) if rightLeftmost else inf, minDiffStartingFrom(root.left), minDiffStartingFrom(root.right))
    return minDiffStartingFrom(root)

但是这个方法显然很烂。根据前面一题的经验，中序遍历之后就是一个排序数组。因此只要检查排序数组相邻的元素即可。

改一下中序遍历即可：

def getMinimumDifference(self, root: TreeNode) -> int:
    if not root: return inf
    stack = []
    cur = root
    prev = inf
    best = inf
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            if best == inf or abs(cur.val - prev) < best:
                best = abs(cur.val - prev)
            prev = cur.val
            cur = cur.right
    return best

501. 二叉搜索树中的众数

带有重复值的BST还真没碰到过。

第一个想法肯定是最简单的：随便来个遍历，加入哈希表就行。

第二个想法就要利用起来BST性质了。所以再次利用中序遍历！

def findMode(self, root: TreeNode) -> List[int]:
    stack = []
    cur = root
    prev = inf
    curCount = 0
    best = 0
    bestVal = []
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            if prev == inf or cur.val == prev:
                curCount += 1
            else:
                # boundary
                if curCount > best:
                    best = curCount
                    bestVal = [prev]
                elif curCount == best:
                    bestVal.append(prev)
                curCount = 1
            prev = cur.val
            cur = cur.right
    # boundary
    if curCount > best:
        best = curCount
        bestVal = [prev]
    elif curCount == best:
        bestVal.append(prev)
    return bestVal

236. 二叉树的最近公共祖先

这题的关键是想到从底向上遍历，因此只能用后序来做。

另外，还包含一个通过递归的返回值来模拟回溯的思想。

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root:
        return None
    if root == p:
        return p
    if root == q:
        return q

    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    if not left and right:
        return right
    if left and not right:
        return left
    return None

235. 二叉搜索树的最近公共祖先

BST是有序的，所以p和q的最近公共祖先就是从上往下第一个落在[p, q]的节点。

lc题解里的说法不错：最近公共祖先就是从根节点出发走到p和q，两条路径上的分叉点。在BST中如果当前节点在[p, q]之外，那么要么一起向左要么一起向右，即还没有到达分叉点。

BST插入删除

插入就直接插就行。

删除理论上就拿leftRightmost或者rightLeftmost填一下完事。但是这里填的时候会产生一点小问题，因为还要变指向这两个节点的指针。最好是分几步操作（以交换leftRightmost为例）：

如果val不等于root.val，就走到子问题里面。
如果val等于root.val:
- temp = root (保存原来的root)
- root = 左子树中的最大值。
- root.left = deleteMin(左子树)。这步递归的删除很重要。
- root.right = temp.right

删除其实很需要一个递归思想，并不简单。代码如下：

def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    def findMax(root):
        if not root:
            return None
        if not root.right:
            return root
        return findMax(root.right)
    def deleteMax(root):
        if not root:
            return None
        if not root.right:
            return root.left
        root.right = deleteMax(root.right)
        return root
    if not root:
        return None
    if key < root.val:
        root.left = self.deleteNode(root.left, key)
    elif key > root.val:
        root.right = self.deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        temp = root
        root = findMax(temp.left)
        root.left = deleteMax(temp.left)
        root.right = temp.right
    return root

669. 修剪二叉搜索树

这里我维持一个invariant：每一层保证root，root.left，root.right落在给定范围内。

def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
    while root and (root.val < low or root.val > high):
        while root and root.val < low:
            root = root.right
        while root and root.val > high:
            root = root.left
    if not root:
        return root
    while root.left and root.left.val < low:
        root.left = root.left.right
    while root.right and root.right.val > high:
        root.right = root.right.left
    self.trimBST(root.left, low, high)
    self.trimBST(root.right, low, high)
    return root

但是注意到这个解法是有冗余的。子问题里的返回值似乎没有用上。

那么如果invariant变成保证root永远在给定范围内是不是就可以了呢？

还真行。

def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
    while root and (root.val < low or root.val > high):
        while root and root.val < low:
            root = root.right
        while root and root.val > high:
            root = root.left
    if not root:
        return root
    root.left = self.trimBST(root.left, low, high)
    root.right = self.trimBST(root.right, low, high)
    return root

构造二叉搜索树

108. 将有序数组转换为二叉搜索树

本题要求平衡，所以root取到最中间的元素就完事了。

正确性证明使用数学归纳法。其关键是证明长度为m和m+1的区间构造出的两棵平衡二叉树，之间的高度差不超过1.

538. 把二叉搜索树转换为累加树

第一个想法：中序排好，算出每个节点的新值，再中序填充。时间空间都是O(n)。

那么怎么使用常数空间？首先的想法是递归，每一层将root应该有的值算好。

每一层的逻辑是root.val + rightLeftmost.val。但是不对。因为左子树没有右子树的信息。

看了题解，发现可以反向中序遍历（右-中-左），这样就不用创建多余的数组了。

def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    sum = 0
    def revInorder(root):
        if not root:
            return
        nonlocal sum
        revInorder(root.right)
        root.val += sum
        sum = root.val
        revInorder(root.left)
    revInorder(root)
    return root

常数空间的话得用到Morris遍历。暂时懒得看了。