刷题第十八天 530.二叉搜索树最小绝对差 501. 二叉搜索中的众数 236. 二叉树最近公共祖先

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

### 变有序数组
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def traversal(result, root):
            if not root:
                return
            traversal(result, root.left)
            result.append(root.val)
            traversal(result, root.right)
        result = []
        traversal(result, root)
        diff = result[1] - result[0]
        for i,val in enumerate(result):
            if i > 1 and result[i] - result[i - 1] < diff:
                diff = result[i] - result[i - 1]
        return diff
 
### 类似双指针，记录前指针的信息
class Solution:
    def __init__(self):
        self.result = float('inf')
        self.pre = None
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if not root:
            return self.result
        left_min = self.getMinimumDifference(root.left)
        if self.pre:
            self.result = min(self.result, root.val - self.pre.val)
        self.pre = root
        right_min = self.getMinimumDifference(root.right)
        return min(left_min, right_min)

二叉搜索树中序遍历完就是一个有序数组，判断数组最小的相邻值 然后返回。

501. 二叉搜索中的众数

class Solution:
    def __init__(self):
        self.result = []
        self.cur_count = 1
        self.max_count = 0
        self.pre = TreeNode(None)
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return self.result
        left_result = self.findMode(root.left)
 
        if not self.pre:
            self.cur_count = 1
        if self.pre.val == root.val:
            self.cur_count += 1
        else:
            self.cur_count = 1
        self.pre = root
 
        if self.cur_count == self.max_count:
            self.result.append(root.val)
        if self.cur_count > self.max_count:
            self.max_count = self.cur_count
            self.result.clear()
            self.result.append(root.val)
 
        right_result = self.findMode(root.right)
        return left_result

中序遍历，主要在于中间的逻辑

1. 前序节点如果不存在，计数为1

2. 前序节点的值等于当前节点的呃值，计数+1

3. 其他情况 计数重新赋为1，并让前序节点更新为当前root

4. 判断目前的累计值是否等于最大计数，如果相等 收获结果，如果大于，则清空数组 ；更新最大计数并收获结果，最后返回result就行

没解决的问题：为什么把倒数后两个if的位置交换 答案就不对，想半天没想明白

解决了：因为如果大于的判断在前面 等于的判断在后面，那么max_count 已经等于cur_count 了之后在等于的判断里面又被加入一次

236. 最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        if root == p or root == q :
            return root
        left = self.lowestCommonAncestor(root.left, p , q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left and right:
            return right
        if not right and left:
            return left
        if right and left:
            return root
        else:
            return None

和计算深度类似，只要碰到节点相等了 就把当前节点返回 然后左右根接住，最后判断左右子树那边接到了 就继续向上返回，直到两边都接到了然后就返回root