20天【代码随想录算法训练营34期】第六章 二叉树part07 （ ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先 ）

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def traversal(self, root) -> list:
        if root is None:
            return []
        return self.traversal(root.left) + [root.val] + self.traversal(root.right)

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        l = self.traversal(root)
        minVal = float('inf')

        for i in range(1, len(l)):
            minVal = min(minVal, abs(l[i] - l[i-1]))
        return minVal

501.二叉搜索树中的众数

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.maxCount = 0
        self.count = 0
        self.pre = None
        self.result = []

    def searchBST(self, cur):
        if cur is None:
            return

        self.searchBST(cur.left)

        if self.pre is None:
            self.count = 1
        elif self.pre.val == cur.val:
            self.count += 1
        else:
            self.count = 1
        self.pre = cur

        if self.count == self.maxCount:
            self.result.append(cur.val)
        
        if self.count > self.maxCount:
            self.maxCount = self.count
            self.result = [cur.val]
        
        self.searchBST(cur.right)
        
        return

    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.count = 0
        self.maxCount = 0
        self.pre = None
        self.result = []

        self.searchBST(root)
        return self.result

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left is not None and right is not None:
            return root

        if left is not None:
            return left
        return right