一、学习视频
【二叉树的最近公共祖先】 https://www.bilibili.com/video/BV1W44y1Z7AR/?share_source=copy_web&vd_source=dc0e55cfae3b304619670a78444fd795
二、跟练代码
1.236. 二叉树的最近公共祖先
（1）后序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 后序遍历
ans = None
def f(node) -> bool:
# 返回是否有目标
nonlocal ans
if not node:
return False
left = f(node.left)
right = f(node.right)
if left and right:
# 左右子树有目标
ans = node
return False # 不需要再找，直接返回False
if node is p or node is q:
# 根节点为目标
if left or right:
# 左或右子树也有目标
ans = node
return False
# 左右无目标
return True
return left or right # 中间节点
f(root)
return ans（2）先序遍历，来自视频代码。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 先序遍历
if root is None or root is p or root is 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 right2.235. 二叉搜索树的最近公共祖先
（1）先序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 先序遍历
if root is None or root is p or root is q:
return root
left = right = None
mx, mn = (p.val, q.val) if p.val > q.val else (q.val, p.val)
if root.val > mn:
left = self.lowestCommonAncestor(root.left, p, q)
if root.val < mx:
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
return right（2）先序优化，来自视频代码。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 先序优化
# 不用判断当前节点是否为空，前提先序
x = root.val
if x > p.val and x > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if x < p.val and x < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root2024.4.23续：
三、课后作业
1.1123. 最深叶节点的最近公共祖先
后序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 后序遍历
def f(node, h):
if node is None:
return h-1, None
l_h, l_node = f(node.left, h+1)
r_h, r_node = f(node.right, h+1)
if l_h == r_h:
return l_h, node
else:
return (l_h, l_node) if l_h > r_h else (r_h, r_node)
_, ans = f(root, 0)
return ans2024.4.28续：
2. 2096. 从二叉树一个节点到另一个节点每一步的方向
最近公共祖先
不会，学习一下，来自灵神题解（. - 力扣（LeetCode））。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
# 公共祖先
def dfs(node, target) -> bool:
nonlocal path
if node is None:
return False
if node.val == target:
# 本节点不需要添加
return True
path.append("L")
if dfs(node.left, target):
return True
# 左边没有
path[-1] = "R"
if dfs(node.right, target):
return True
# 右边没有
path.pop() #都没有，去掉当前路径
return False
path = []
dfs(root, startValue)
pathToStart = path
path = []
dfs(root, destValue)
pathToDest = path
while len(pathToStart) > 0 and len(pathToDest) > 0 and pathToStart[0] == pathToDest[0]:
pathToStart.pop(0)
pathToDest.pop(0)
return "U" * len(pathToStart) + "".join(pathToDest)还有另一种写法，来自评论（. - 力扣（LeetCode））。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
# 公共祖先
def dfs(node: Optional[TreeNode]):
if node is None:
return
nonlocal d, path
if node.val in [startValue, destValue]:
d[node.val] = path.copy()
if len(d) == 2:
# 找到起终两个节点
return
# 添加路径
path.append("L")
dfs(node.left)
path[-1] = "R"
dfs(node.right)
path.pop() # 去掉当前方向
d, path = {}, []
dfs(root)
# 找出从根节点到s, t路径的共同长度
i = 0
n, m = len(d[startValue]), len(d[destValue])
while i < n and i < m and d[startValue][i] == d[destValue][i]:
i += 1
return "U" * (n - i) + "".join(d[destValue][i:])完
感谢你看到这里！一起加油吧！
