前言

今天是算法训练营的第十八天（并不是），本文的撰写时间实际上已经是对于训练营第三十四天了，由于寒假时间太长，惰性难以避免地放大到了最大化。

废话不多说，总之还是希望在开学前能把文档进度追回来吧…..

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

题目链接：530. 二叉搜索树的最小绝对差

题目描述：

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

思路

这道题我的思路比较简单，使用层序遍历将二叉树所有节点保存下来，最后将保存下来的数值排序遍历找到最小差值。（回头看这样做有点笨，明明对二叉搜索树中序遍历直接就是得到一个有序的数组）

完整实现代码

# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if not root:
            return
        queue = collections.deque([root])
        ans = inf
        arr = []
        while queue:
            levelSize = len(queue)
            for _ in range(levelSize):
                node = queue.popleft()
                arr.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        arr.sort()
        for i in range(1, len(arr)):
            ans = min(ans, abs(arr[i] - arr[i - 1]))
        return ans

501.二叉搜索树中的众数

题目链接：501. 二叉搜索树中的众数

题目描述：

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

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

思路

面对这种需要遍历二叉树中所有元素的情况，之前刷题的时候明显偏向使用层序遍历，这里的做法依旧是使用层序遍历对树的节点值进行记录，记录的同时使用一个字典来记录数量，最后输出最大数量的值即为众数。

完整代码实现

# 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 findMode(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return 
            
        queue = collections.deque([root])
        map1 = {}
        ans = []
        while queue:
            levelSize = len(queue)
            for _ in range(levelSize):
                node = queue.popleft()
                map1[node.val] = map1.get(node.val, 0) + 1
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
        max1 = max(map1.values())
        for idx, val in map1.items():
            if val == max1:
                ans.append(idx)
        return ans

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

题目链接：236. 二叉树的最近公共祖先

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

这道题当时做的时候就觉得有点难想到，现在再看依旧觉得有点抽象。

我们在这里需要使用到一些回溯的技巧，处理逻辑大致为：判断左子树和右子树中有没有找到p或q，如果左右子树中同时找到，那么说明当前节点就是我们需要的目标，向上返回即可；如果左子树中找到，那么返回左子树；如果右子树中找到，返回右子树。一趟回溯下来，由于是自底向上，所以我们不必担心最终返回的值是否是最近的公共祖先。

整体代码实现

# 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 == p or root == q:
            return root
        if not root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left != None and right != None:
            return root
        if left != None and right == None:
            return left
        elif left == None and right != None:
            return right
        else:
            return None

总结

今天前面两题主要解决思路是对整棵树进行遍历，并把数值采集，最后对采集下来的数值进行判断处理。最后一道题略微使用到了一点回溯的技巧，写这篇文章的时候已经完整把回溯篇章的题目刷完，所以现在再看理解难度其实没有初见那么高，但是依旧值得下一次的深究。