530.二叉搜索树的最小绝对差
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
stack = []
cur = root
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(abs(cur.val-pre.val),res)
pre = cur
cur = cur.right
return res
501. 二叉搜索树中的众数
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
stack = []
cur = root
pre = None
res = []
maxcount,count = 0,0
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre == None:
count =1
elif cur.val == pre.val:
count +=1
else:
count =1
if count == maxcount:
res.append(cur.val)
if count > maxcount:
maxcount=count
res.clear()
res.append(cur.val)
pre = cur
cur = cur.right
return res
236. 二叉树的最近公共祖先
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> '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
return right
