二叉搜素树，利用中序遍历的升序结果
530.二叉搜索树的最小绝对差
1、递归中序遍历
class Solution:
def __init__(self):
self.pre = None
self.res = float('inf')
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.traversal(root)
return self.res
def traversal(self, cur):
if cur is None:
return
# 左
self.traversal(cur.left)
# 中
if self.pre:
self.res = min(self.res, cur.val - self.pre.val)
self.pre = cur
# 右
self.traversal(cur.right)
2、迭代中序遍历
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
stack = []
cur = root
pre = None
min_val = float('inf')
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre:
min_val = min(min_val, cur.val - pre.val)
pre = cur
cur = cur.right
return min_val
3、统一写法迭代
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
stack = [root]
pre = None
min_val = float('inf')
while stack:
node = stack.pop()
# 查找节点
if node:
# 右
if node.right:
stack.append(node.right)
# 中
stack.append(node)
stack.append(None)
# 左
if node.left:
stack.append(node.left)
# 处理节点
else:
node = stack.pop()
if pre:
min_val = min(min_val, node.val-pre.val)
pre = node
return min_val
501.二叉搜索树中的众数
1、递归+pre 指针
class Solution:
def __init__(self):
self.pre = None
self.res = []
self.count = 0
self.max_count = 0
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.travesal(root)
return self.res
def travesal(self, cur):
if cur is None:
return
# 左
self.travesal(cur.left)
# 中
if self.pre:
if self.pre.val == cur.val:
self.count += 1
# 不相等
else:
self.count = 1
# 第一次
else:
self.count = 1
if self.count == self.max_count:
self.res.append(cur.val)
if self.count > self.max_count:
self.max_count = self.count
self.res.clear()
self.res.append(cur.val)
self.pre = cur
# 右
self.travesal(cur.right)
2、迭代法
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
res = []
if root is None:
return res
cur = root
stack = []
pre = None
max_count, count = 0, 0
while cur or stack:
# 左
if cur:
stack.append(cur)
cur = cur.left
else:
# 中
cur = stack.pop()
if pre:
if pre.val == cur.val:
count += 1
else:
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
236. 二叉树的最近公共祖先
确定使用后序遍历
1、递归法
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 终止条件
if root is 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
elif left and not right:
return left
elif right and not left:
return right
else:
return None