700.二叉搜索树中的搜索

link

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

二叉搜索树：每个节点都满足：左节点 < 当前节点 < 右节点。

思路

前序遍历当前树，判断是进入左子树还是右子树。迭代法较为简便，可以直接 return 来返回结果。

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        stack = []
        if root:
            stack.append(root)
        while stack:
            cur = stack.pop()

            if cur.val == val:
                return cur
            elif cur.val > val:
                if cur.left:
                    stack.append(cur.left)
                else:
                    return None
            
            elif cur.val < val:
                if cur.right:
                    stack.append(cur.right)
                else:
                    return None

更简便的方法：直接进行遍历，不需要使用栈来维护调用顺序

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root:
            if val < root.val: root = root.left
            elif val > root.val: root = root.right
            else: return root
        return None

98.验证二叉搜索树

link

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思路

题目中暗含的是，判断当前节点是否满足，然后遍历左右子树，本质上是前序遍历。但是，不能单纯的比较左节点小于中间节点，右节点大于中间节点，要比较的是左子树所有节点小于中间节点，右子树所有节点大于中间节点。所以需要进行中序遍历。

注意中序遍历下，二叉搜索树的结果为有序数组，所以只需要判断中序遍历的结果是否为有序数组即可。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = []
        def eval(node):
            if node.left:
                eval(node.left)
            res.append(node.val)
            if node.right:
                eval(node.right)
        if root:
            eval(root)
        for i in range(len(res) - 1):
            if res[i] >= res[i+1]:
                return False
        return True

也可以直接在中序遍历的过程中判断，只需要记录前一个访问的节点，然后判断是否是升序即可。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        res = []
        stack = []
        cur = root
        pre = float('-inf')
        while True:
            while cur != None:
                stack.append(cur)
                cur = cur.left
            
            if len(stack) == 0:
                break
            cur = stack.pop()

            if cur.val <= pre:
                return False
            else:
                pre = cur.val
            cur = cur.right

        return True

（来自 gpt）此外，也可以维护一个区间，通过递归判断一个节点是否在指定的范围中：

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, lower=float('-inf'), upper=float('inf')):
            if not node:
                return True
            if not (lower < node.val < upper):
                return False
            return (validate(node.left, lower, node.val) and
                    validate(node.right, node.val, upper))
        return validate(root)

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

link

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。所有节点均为正数。

思路

中序遍历，然后在结果数组中依次判断相邻的节点。

也可以像前一题一样记录上一次访问的数，直接判断。

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        res = []
        stack = []
        cur = root
        pre = None
        mindif = float('inf')
        while True:
            while cur != None:
                stack.append(cur)
                cur = cur.left
            
            if len(stack) == 0:
                break
            cur = stack.pop()

            if pre != None:
                mindif = min(mindif, cur.val - pre)
           
            pre = cur.val
            cur = cur.right

        return mindif

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。

501.二叉搜索树中的众数

link

二叉搜索树放宽条件：

结点左子树中所含节点的值小于等于当前节点的值
结点右子树中所含节点的值大于等于当前节点的值
左子树和右子树都是二叉搜索树

思路

简单做法仍然是在遍历结果中寻找。

如果在遍历的过程中进行处理，中序遍历的结果是升序，所以和上一题一样，记录上一个值，如果相同则 count 加一。同时需要记录 maxcount，如果当前的 count 大于 maxcount，则将结果清空再加入当前元素。

class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        maxcount = 0
        count = 0
        res = []
        stack = []
        cur = root
        pre = None
        while True:
            while cur!= None:
                stack.append(cur)
                cur = cur.left
            
            if len(stack) == 0:
                break
            cur = stack.pop()

            if pre != None and pre == cur.val:
                count += 1
            else: # 有新数字出现 or 第一个数字
                count = 1

            if count > maxcount:
                res.clear()
                res.append(cur.val)
                maxcount = count
            elif count == maxcount:
                res.append(cur.val)

            pre = cur.val
            cur = cur.right
        return res

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

link

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

思路

节点 node 的新值等于原树中大于或等于 node.val 的值之和。而二叉搜索树中序遍历是升序排列。如果我们从右到左中序遍历（右 → 根 → 左），就会得到降序序列。就可以从大到小进行累加。

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack = []
        s = 0
        cur = root
        while True:
            while cur:
                stack.append(cur)
                cur = cur.right
            
            if len(stack) == 0:
                break
            cur = stack.pop()
            s += cur.val
            cur.val = s
            cur = cur.left
        
        return root