代码随想录27期|Python|Day21|二叉树| 530.二叉搜索树的最小绝对差| 501.二叉搜索树中的众数| 236. 二叉树的最近公共祖先

特别需要注意题目中给的隐藏信息（比如这里的BST）?

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

前两个是BST的经典递归模版解法，后面一个迭代的解法可以当作BST的一般迭代规则。

转换成数组

根据一般的递归模版

    def traversal(self, root):
        if not root:
            return
        self.traversal(root.left)
        self.vec.append(root.val)
        self.traversal(root.right)

在根据Day20的查找元素for循环的方法进行数组的遍历。?

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

    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.vec = []
        result = float('inf')
        self.traversal(root)
        # 在有序数组里面，最小值只可能是相邻的
        for i in range(1, len(self.vec)):
            if self.vec[i] - self.vec[i - 1] <= result:
                result = self.vec[i] - self.vec[i - 1]
        return result

    def traversal(self, root):
        if not root:
            return
        self.traversal(root.left)
        self.vec.append(root.val)
        self.traversal(root.right)

设定+更新最小值

在查找BST的基础上加入更新全局最小值的操作。

注意if pre is not None的判断语句用来排除初始化情况。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.min_value = float('inf')  # 初始化为最大的int之外的数字
        self.pre = None

    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 递归法
        self.traversal_2(root)
        return self.min_value
    
    def traversal_2(self, root):
        if not root:
            return
        self.traversal_2(root.left)
        if self.pre is not None:
            self.min_value = min(self.min_value, root.val - self.pre.val)
        self.pre = root
        self.traversal_2(root.right)

迭代法（BST的一般迭代过程）

    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # 迭代法
        stack = []
        pre = None
        cur = root
        global_min = float('inf')
        
        # 当前不是空节点或者栈里还有没有遍历完的元素的时候
        while cur is not None or len(stack) > 0:
            # 遍历所有的左侧节点（先找最小值）
            if cur is not None:
                stack.append(cur)
                cur = cur.left
            else:
                # 依次回溯
                cur = stack.pop()
                if pre is not None:
                    global_min = min(global_min, cur.val - pre.val)
                pre = cur
                cur = cur.right
        return global_min

其中注意到和找最小值递归类似，都存在一个固定的模版函数体：

                """
                左侧节点处理
                """
                if pre is not None:
                    global_min = min(global_min, cur.val - pre.val)
                pre = cur
                """
                右侧节点处理
                """

从这个过程我们也可以看出，右侧节点的处理仅仅是完成了一个位置的移动，所以我们不妨只从左侧子树的遍历（斜着遍历）看一个BST。

501.?二叉搜索树中的众数

字典+for循环遍历（算两遍）

先找到频率对应的字典，然后找频率的最大值。

缺点是对于时间要求比较高。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import defaultdict
class Solution(object):
    def BSTsearch(self, cur, freq_map):
        if cur is None:
            return
        freq_map[cur.val] += 1  # 统计出现频率
        self.BSTsearch(cur.left, freq_map)
        self.BSTsearch(cur.right, freq_map)

    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 字典统计+算两遍
        freq_map = defaultdict(int)  # 初始化字典
        res = []
        if not root:
            return res
        self.BSTsearch(root, freq_map)
        # 取出最大值
        max_freq = max(freq_map.values())
        for key, freq in freq_map.items():
            if freq == max_freq:  # 算两遍找最大值
                res.append(key)
        return res

BST性质搜索+双指针

利用BST性质，相同的字符（如果存在）必定是连续的（单调性），所以只需要算连续出现的频率即可。

需要注意：res结果保存树数组在找到新的最大频率之后需要进行及时的更新。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import defaultdict

class Solution(object):
    def __init__(self):
        self.res = []
        self.pre = None
        self.max_freq = 0
        self.cur_freq = 0

    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 双指针
        self.BSTsearch_2(root)
        return self.res

    def BSTsearch_2(self, cur):
        if not cur:
            return

        self.BSTsearch_2(cur.left)

        if self.pre is None:  # 前一个节点是空节点说明现在的节点是叶子节点，初始化为1
            self.cur_freq = 1
        elif cur.val == self.pre.val:  # 和前一个节点相等 + 1
            self.cur_freq += 1
        else:  # 和前一个节点不相等，初始化为1
            self.cur_freq = 1
        self.pre = cur

        if self.cur_freq == self.max_freq:
            self.res.append(cur.val)
        elif self.cur_freq > self.max_freq:
            # 注意全局变量的更新，特别是答案数组的更新
            self.max_freq = self.cur_freq
            self.res = [cur.val]

        self.BSTsearch_2(cur.right)
        return 

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

注意题目条件：所有的数值都不相同。

一个基本的思路：只要找到了距离p、q深度最小的一个节点，使得其左右节点有一个包含p、q中的某一个，那么这个节点就是要找的节点。

但是遇到一个问题：如果另外一个节点不在这个根节点的子树里面。这是需要运用到递归的思想，也就是返回值是返回给上一层根节点的值，也就是root是返回给上一层root的，在上一个函数当中还会进一步递归。

这里引入一个返回值实际上是root的“标记值”的概念：只在一个当前root的子树当中找到了一个目标值，也就意味着上一层的root被标记为这个root的值，在上一层的root左右子树没有找到另外一个值的时候，更新标记的root为上一层，再往上返回递归。其实也就是一个回溯的过程。

这个过程的实现体现在以下的函数结构当中：

        if left != None and right != None:  # 当前左右都找到，返回当前节点（就是要找的）
            return root
        # 左或者右没找到，返回找到的那个给中间节点（代表这个子树包含了其中一个）
        if left == None and right != None:
            return right
        elif left != None and right == None:
            return left
        else:  # 其他情况说明不在这个子树里
            return None

也可以简化为：?

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

        if left is None:
            return right
        return left

本题需要从p、q（也就是底层）出发，向上找根节点，所以顺序采用的是后序遍历+回溯的方法。

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

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        # 终止条件：当前节点是空 或者 找到了p、q中的一个节点
        if not root:
            return root
        elif root == p or root == q:
            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 right
        elif left != None and right == None:
            return left
        else:  # 其他情况说明不在这个子树里
            return None

还有一个困惑：为什么一定要遍历整个树？是否只需要找到一个路径就返回？

实际上不可以，因为往上返回的值是依赖左右子树搜索的反馈进行的，也就是说需要左右子树的返回结果的时候，即使是“找到一个满足条件的即可”也需要遍历整个树。

OMG第21天完结🎉