代码随想录算法训练营 Day 16
Published:
Q1. LeetCode 530
思路 - 中序遍历
二叉搜索树保证了左<中<右
解法1. 递归法（获得遍历结果然后计算最小值）
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
arr = []
def dfs(node):
if not node:
return
dfs(node.left)
arr.append(node.val)
dfs(node.right)
dfs(root)
res = float('inf')
for i in range(1, len(arr)):
res = min(res, arr[i] - arr[i - 1])
return res
解法2: 递归法（遍历过程中统计最小值）
class Solution:
def __init__(self):
self.res = float('inf')
self.pre = None
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
if not root:
return
self.getMinimumDifference(root.left)
if self.pre:
self.res = min(self.res, root.val - self.pre.val)
self.pre = root
self.getMinimumDifference(root.right)
return self.res
解法3: 迭代法
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
res = float('inf')
prev = None
stack = [root]
while stack:
curr = stack.pop()
if curr:
if curr.right:
stack.append(curr.right)
stack.append(curr)
stack.append(None)
if curr.left:
stack.append(curr.left)
else:
curr = stack.pop()
if prev:
res = min(res, curr.val - prev.val)
prev = curr
return res
Q2. LeetCode 501
解法1: 通过任何遍历方式，统计每个元素出现的次数（非二叉搜索树的解决方法）
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
arr = defaultdict(int)
def dfs(node):
if not node:
return
arr[node.val] += 1
dfs(node.left)
dfs(node.right)
if not root:
return []
dfs(root)
res = []
max_freq = max(arr.values())
for num, freq in arr.items():
if freq == max_freq:
res.append(num)
return res
解法2: 二叉搜索树的性质决定当使用中序遍历时，只需要比较当前节点和之前节点是否相同。通过max_freq变量统计当前最大频率，因此不需要额外的空间开销
注意：max_freq可能会随着遍历而修改，在每次修改的过程中，需要将之前的结果数组清空
class Solution:
def __init__(self):
self.res = []
# 统计当前的最大频率
self.max_freq = 0
self.prev = None
self.count = 0
def findMode(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return
self.findMode(root.left)
if not self.prev:
self.count = 1
elif root.val == self.prev.val:
self.count += 1
else:
self.count = 1
self.prev = root
if self.count == self.max_freq:
self.res.append(root.val)
if self.count > self.max_freq:
self.max_freq = self.count
self.res = [root.val]
self.findMode(root.right)
return self.res
解法3: 迭代法
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res = []
stack = [root]
prev = None
max_freq = 0
count = 0
while stack:
curr = stack.pop()
if curr:
if curr.right:
stack.append(curr.right)
stack.append(curr)
stack.append(None)
if curr.left:
stack.append(curr.left)
else:
curr = stack.pop()
if not prev:
count = 1
elif curr.val == prev.val:
count += 1
else:
count = 1
prev = curr
if count > max_freq:
max_freq = count
res = []
if count == max_freq:
res.append(curr.val)
return res
Q3. LeetCode 236
思路 - 后序遍历
先在左右子树中分别寻找匹配项，在中间节点根据返回结果求解
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(node):
if not node:
return None
if node == p or node == q:
return node
# 左右节点
l = dfs(node.left)
r = dfs(node.right)
# 中间节点
# 在左子树和右子树中找到了p和q - 返回当前节点
if l and r:
return node
# 只在右子树中找到匹配项 - 返回有节点
elif not l and r:
return r
elif not r and l:
return l
return None
res = dfs(root)
return res
Take some notes
求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的l和r）做逻辑判断。
代码中包含了最小公共祖先为其中某个节点的特殊情况（第二个if判断条件）