530. 二叉搜索树的最小绝对差
- 思路
- example
- 返回 树中任意两不同节点值之间的最小差值
- 二叉搜索树(BST): 对应有序（递增）数组 （中序遍历）
- 最小差值肯定在相邻两个元素间取得。（如果求最大绝对差只需第1个和最后1个的绝对差）
- 解法1：递归，中序遍历转化为有序数组，额外空间
- 复杂度. 时间：O(n), 空间: O(n
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def traversal(root):
if root == None:
return
traversal(root.left)
nums.append(root.val)
traversal(root.right)
nums = []
traversal(root)
res = float('inf')
for i in range(1, len(nums)):
res = min(res, abs(nums[i] - nums[i-1]))
return res
- 解法2：递归，中序遍历，维护pre节点
- 可看成是在BST上的双指针(pre, cur), 同向
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal pre, res
if root == None:
return
traversal(root.left)
if pre:
res = min(res, abs(pre.val - root.val))
pre = root
traversal(root.right)
pre = None
res = float('inf')
traversal(root)
return res
- 解法3：迭代，中序遍历，维护pre节点
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
cur = root
stack = []
pre = None
res = float('inf')
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre:
res = min(res, abs(pre.val - cur.val))
pre = cur
cur = cur.right
return res
- 重复题：783. 二叉搜索树节点最小距离
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal pre, res
if root == None:
return
traversal(root.left)
if pre:
res = min(res, abs(root.val - pre.val))
pre = root
traversal(root.right)
pre = None
res = float('inf')
traversal(root)
return res
501. 二叉搜索树中的众数
- 思路
- example
- 含重复值
- 有序数组累计频率
- 递归，中序，维护pre节点， 双指针
- pre节点
- max_freq
- cur_freq
- res = [] 保存结果
- 复杂度. 时间：O(n), 空间: O(1) （如果递归栈不算在内）
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root):
nonlocal pre, cnt, cnt_max, res
if root == None:
return
traversal(root.left)
if pre:
if root.val == pre.val:
cnt += 1
else:
cnt = 1
else:
cnt = 1
if cnt > cnt_max:
cnt_max = cnt
res = [root.val]
elif cnt == cnt_max:
res.append(root.val)
pre = root
traversal(root.right)
cnt, cnt_max = -1, -float('inf')
pre = None
res = []
traversal(root)
return res
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root):
nonlocal pre, cnt, max_cnt
nonlocal res # !!!
if root == None:
return
traversal(root.left)
if pre == None:
cnt = 1
else:
if root.val == pre.val:
cnt += 1
else:
cnt = 1
if cnt > max_cnt:
max_cnt = cnt
res = [root.val]
elif cnt == max_cnt:
res.append(root.val)
pre = root
traversal(root.right)
res = []
pre = None
cnt, max_cnt = 0, 0
traversal(root)
return res
236. 二叉树的最近公共祖先
- 思路
- example
- 所有 Node.val 互不相同.
- p and q will exist in the tree.
- 递归dfs，前序，回溯，自上而下，保存根节点到p，q的两条路径
- 在路径中找最近公共祖先
- 更直观。
- 比较多细节。
- 适用更一般的情况。
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traversal(root, targetNode):
if root == targetNode:
paths.append(path[:])
return
if root.left:
path.append(root.left)
traversal(root.left, targetNode)
path.pop()
if root.right:
path.append(root.right)
traversal(root.right, targetNode)
path.pop()
paths = [] # save path results
path = [root] # local path
traversal(root, p)
traversal(root, q)
ancestor = None
for i in range(min(len(paths[0]), len(paths[1]))):
if paths[0][i] == paths[1][i]:
ancestor = paths[0][i]
else:
break
return ancestor
- 上面的代码递归找path的时候仍然遍历了整棵树。
- 优化：提早return
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traversal(root, targetNode):
if root == targetNode:
paths.append(path[:])
return True
if root.left:
path.append(root.left)
if traversal(root.left, targetNode):
return True
path.pop()
if root.right:
path.append(root.right)
if traversal(root.right, targetNode):
return True
path.pop()
return False
paths = [] # save path results
path = [root]
traversal(root, p)
path = [root] # 需要重新初始化！！！
traversal(root, q)
ancestor = None
for i in range(min(len(paths[0]), len(paths[1]))):
if paths[0][i] == paths[1][i]:
ancestor = paths[0][i]
else:
break
return ancestor
- 递归，后序，自下而上，回溯
返回值：p, q, None, 或者LCA(p,q)
- 遍历整棵树
- 不直观, 注意Base Case的逻辑。
- 前提：树中必有p,q节点，并且树中节点数值各不相同！！！
- def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
-
函数意义:
- 树中含有p,q时，返回最近公共祖先
- 树中只含p或q的一个时，返回相应的节点
- 树中不含p和q时，返回None
- 后序：结合左子树与右子树遍历结果
- 如果左子树含有p,q。那么左子树返回结果即为答案。如果右子树含有p,q. 那到右子树返回结果即为答案。
- 如果左子树只含q,q中的一个，返回左子树结果。如果右子树只含q,q中的一个，返回右子树结果。
-
函数意义:
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == None:
return None
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
if left == None:
return right
if right == None:
return left
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traversal(root):
if root == None:
return None
if root == p or root == q:
return root
left = traversal(root.left)
right = traversal(root.right)
if left == None:
return right
if right == None:
return left
return root
return traversal(root)
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == None:
return None
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if root.val == p.val or root.val == q.val:
return root
if left and right == None:
return left
if left == None and right:
return right
if left == None and right == None:
return None
if left and right:
return root
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traverse(root):
if root == None:
return None
left = traverse(root.left)
right = traverse(root.right)
if root == p or root == q:
return root
if left == p and right == q:
return root
if left == q and right == p:
return root
if left != None:
return left
if right != None:
return right
return None
return traverse(root)
