二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]
1. 在主函数中求众数，也就是在有序序列中求众数。
2. 因为可能存在多个众数，我们用 cnt 记录当前元素重复的次数，
用 maxCnt 记录已经遍历过的元素当中出现最多的元素的出现次数，用 res 记录众数。
# 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]:
lst = []
self.In0rder(root, lst)
# 记录前一个元素值
pre = lst[0]
# 记录次数
cnt = 1
# 记录最大次数
maxCnt = 1
# 记录结果
res = [lst[0]]
for i in range(1, len(lst)):
# 如果与前一个节点的值相等
if pre == lst[i]:
cnt += 1
else:
cnt = 1
# 如果和最大次数相同，将值放入res
if cnt == maxCnt:
res.append(lst[i])
# 如果大于最大次数
if cnt > maxCnt:
# 更新最大次数
maxCnt = cnt
# 重新更新res
res = [lst[i]]
pre = lst[i]
return res
二叉树最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode' ) -> 'TreeNode':
# 1、如果此时访问的节点 root 为 null，那么直接返回 null
if not root:
return None
# 2、如果此时访问的节点 root 为指定节点 p，那么返回 p 这个节点
if root == p : return p
# 3、如果此时访问的节点 root 为指定节点 q，那么返回 q 这个节点
if root == q : return q
# 4、经过上面 1、2、3 的判断之后，root 这个节点必然不是 p、q、null 这三种情况的节点
# 接下来，去递归的判断当前节点 root 的左右子树是否包含 p 、q 这两个指定节点
# 5、递归的去查找 root 的左子树，判断是否包含p 、q 这两个指定节点
# 如果 root 的左子树节点和它的左子树所有节点中包含 p，那么 left 的值就是 p
# 如果 root 的左子树节点和它的左子树所有节点中包含 q，那么 left 的值就是 q
# 如果 root 的左子树节点和它的左子树所有节点中既不包含 p，也不包含 q，那么 left 的值就是 null
left = self.lowestCommonAncestor(root.left,p,q)
# 6、递归的去查找 root 的右子树，判断是否包含p 、q 这两个指定节点
# 如果 root 的右子树节点和它的右子树所有节点中包含 p，那么 right 的值就是 p
# 如果 root 的右子树节点和它的右子树所有节点中包含 q，那么 right 的值就是 q
# 如果 root 的右子树节点和它的右子树所有节点中既不包含 p，也不包含 q，那么 right 的值就是 null
right = self.lowestCommonAncestor(root.right,p,q)
# 7、判断完当前节点 root 、 root 的左子树 left、root 的右子树 right 的情况后
# 开始向父节点传递信息
# 8、如果 root 节点的左子树 left 和右子树 right 都没有找到指定节点 p、q
# 并且 root 自己本身也不是指定节点 p、q
# 那么它给父节点传递的信息就是以 root 为根节点的那颗二叉树没有指定节点 p、q
if not left and not right :
# 返回 null，告诉 root 的父节点，这里没找到指定节点 p、q
return None
# 9、如果在 root 节点的左子树 left 中没有找到指定节点 p、q
# 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q 完全取决于 right 了
elif not left :
# 返回 right ，告诉 root 的父节点，能不能找到指定节点 p、q 完全取决于 right
return right
# 10、如果在 root 节点的右子树 right 中没有找到指定节点 p、q
# 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q 完全取决于 left 了
elif not right :
# 返回 left ，告诉 root 的父节点，能不能找到指定节点 p、q 完全取决于 left
return left
# 11、此时，left != null 并且 right != null
# 这说明在以 root 节点为根节点的那棵二叉树中找到了指定节点 p ，也找到了指定节点 q
# 那么就告诉父节点，root 就是 p、q 的最近公共祖先
else:
# 返回 root ，告诉 root 的父节点，root 就是 p、q 的最近公共祖先
return root
