题目简介
530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
501. 二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
初见思路
今天的题目，关键词是BST。 要牢牢记住501题干写的BST的特性。
530.尝试用迭代法解决
class Solution:
def getMinimumDifference(self, root):
stack = []
cur = root
pre = None
result = float('inf')
while cur or stack:
if cur:
stack.append(cur) # 将访问的节点放进栈
cur = cur.left # 左
else:
cur = stack.pop()
if pre: # 中
result = min(result, cur.val - pre.val)
pre = cur
cur = cur.right # 右
return result
- 迭代怎么想？
class Solution:
def findMode(self, root):
st = []
cur = root
pre = None
maxCount = 0 # 最大频率
count = 0 # 统计频率
result = []
while cur is not None or st:
if cur is not None: # 指针来访问节点，访问到最底层
st.append(cur) # 将访问的节点放进栈
cur = cur.left # 左
else:
cur = st.pop()
if pre is None: # 第一个节点
count = 1
elif pre.val == cur.val: # 与前一个节点数值相同
count += 1
else: # 与前一个节点数值不同
count = 1
if count == maxCount: # 如果和最大值相同，放进result中
result.append(cur.val)
if count > maxCount: # 如果计数大于最大值频率
maxCount = count # 更新最大频率
pre = cur
cur = cur.right # 右
return result
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root==p or root==q:
return root
left_child = self.lowestCommonAncestor(root.left, p, q)
right_child = self.lowestCommonAncestor(root.right, p, q)
if not left_child and not right_child:
return None
if not left_child:
return right_child
if not right_child:
return left_child
return root
