1.530.二叉搜索树的最小绝对差
题目链接:530.二叉搜索树的最小绝对差
文档讲解: 代码随想录
学会在递归遍历的过程中记录前后两个指针,而且二叉搜索树是有序的,需要利用这个特性来作题。我感觉和昨天验证是否是有效二叉搜索树的思路是一样的。
利用中序递增,结合数组
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
vec = []
self.traversal(root, vec)
minn = float('inf')
for i in range(1,len(vec)):
if vec[i] - vec[i - 1] < minn:
minn = vec[i] - vec[i - 1]
return minn
def traversal(self, node, vec):
#中序递归遍历
if not node:
return
self.traversal(node.left, vec)
vec.append(node.val)
self.traversal(node.right, vec)
利用中序递增找到该树最小值
class Solution(object):
def __init__(self):
self.pre = None
self.res = float('inf')
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.traversal(root)
return self.res
def traversal(self, node):
if not node:
return
self.traversal(node.left)
if self.pre and node.val - self.pre.val < self.res:
self.res = node.val - self.pre.val
self.pre = node
self.traversal(node.right)
迭代法
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
stack = []
cur = root
pre = None
res = float('inf')
while cur or stack:#是or不是and,因为cur可能为空
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre and cur.val - pre.val < res:
res = cur.val - pre.val
pre = cur
cur = cur.right
return res
2.501.二叉搜索树中的众数
题目链接:501.二叉搜索树中的众数
文档讲解: 代码随想录
递归法,利用字典,针对普通二叉树
class Solution(object):
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
#遍历,统计出现频率,输出元素
if not root:
return []
res = []
freq_map = defaultdict(int)
self.searchBTS(root, freq_map)
max_freq = max(freq_map.values())
for key, value in freq_map.items():
if value == max_freq:
res.append(key)
return res
def searchBTS(self, node, freq_map):
if not node:
return
freq_map[node.val] += 1
self.searchBTS(node.left,freq_map)
self.searchBTS(node.right,freq_map)
递归法,利用二叉搜索树有序的特性
class Solution(object):
def __init__(self):
self.count = 0
self.pre = None
self.max_count = 0
self.res = []
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
#利用二叉搜索树的特性,中序遍历有序
self.count = 0
self.max_count = 0
self.pre = None
self.res = []
self.traversal(root)
return self.res
def traversal(self, node):
if not node:
return
self.traversal(node.left)
if not self.pre:
self.count = 1
elif self.pre.val == node.val:
self.count += 1
else:
self.count = 1
self.pre = node
if self.count == self.max_count:#本来以为这个不用,但忽略了可能有很多频率一样的元素
self.res.append(node.val)
if self.count > self.max_count:
self.max_count = self.count
self.res = [node.val]
self.traversal(node.right)
迭代法:用的统一迭代中的中序遍历
class Solution(object):
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
stack = []
res = []
cur = root
pre = None
max_count = 0
count = 0
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if not pre:
count = 1
elif pre.val == cur.val:
count += 1
else:
count = 1
if count == max_count:
res.append(cur.val)
if count > max_count:
max_count = count
res = [cur.val]
pre = cur
cur = cur.right
return res
3.236. 二叉树的最近公共祖先
题目链接:236. 二叉树的最近公共祖先
文档讲解: 代码随想录
求最近公共祖先,需要从底向上遍历,因此采用后序遍历。在回溯过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点都遍历,因为要使用递归函数的返回值做逻辑判断。
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: 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 left and right:
return root
elif not left and right:
return right
elif left and not right:
return left
else:
return None
精简版:
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
else:
return right