530. 二叉搜索樹的最小絕對差
- 思路
- example
- 返回 樹中任意兩不同節(jié)點值之間的最小差值
- 二叉搜索樹(BST): 對應(yīng)有序（遞增）數(shù)組 （中序遍歷）
- 最小差值肯定在相鄰兩個元素間取得问欠。（如果求最大絕對差只需第1個和最后1個的絕對差）
- 解法1：遞歸挠唆，中序遍歷轉(zhuǎn)化為有序數(shù)組兔沃，額外空間
- 復(fù)雜度. 時間：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：遞歸，中序遍歷审葬，維護(hù)pre節(jié)點
- 可看成是在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：迭代，中序遍歷，維護(hù)pre節(jié)點
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
- 重復(fù)題：783. 二叉搜索樹節(jié)點最小距離
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. 二叉搜索樹中的眾數(shù)
- 思路
- example
- 含重復(fù)值
- 有序數(shù)組累計頻率
- 遞歸倍踪，中序瓣窄，維護(hù)pre節(jié)點笛厦， 雙指針
- pre節(jié)點
- max_freq
- cur_freq
- res = [] 保存結(jié)果
- 復(fù)雜度. 時間：O(n), 空間: O(1) （如果遞歸棧不算在內(nèi)）
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，前序俺夕，回溯裳凸，自上而下贱鄙，保存根節(jié)點到p，q的兩條路徑
- 在路徑中找最近公共祖先
- 更直觀姨谷。
- 比較多細(xì)節(jié)逗宁。
- 適用更一般的情況。
- 復(fù)雜度. 時間：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的時候仍然遍歷了整棵樹梦湘。
- 優(yōu)化：提早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節(jié)點，并且樹中節(jié)點數(shù)值各不相同Ｅ丁Ｆⅰ！
- def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
-
函數(shù)意義:
- 樹中含有p,q時守谓，返回最近公共祖先
- 樹中只含p或q的一個時穿铆，返回相應(yīng)的節(jié)點
- 樹中不含p和q時，返回None
- 后序：結(jié)合左子樹與右子樹遍歷結(jié)果
- 如果左子樹含有p,q斋荞。那么左子樹返回結(jié)果即為答案荞雏。如果右子樹含有p,q. 那到右子樹返回結(jié)果即為答案。
- 如果左子樹只含q,q中的一個平酿，返回左子樹結(jié)果凤优。如果右子樹只含q,q中的一個，返回右子樹結(jié)果蜈彼。
-
函數(shù)意義:
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)
