2024.4.（22，23，28号）力扣刷题记录-二叉树学习记录4

本文主要是介绍2024.4.（22，23，28号）力扣刷题记录-二叉树学习记录4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、学习视频

【二叉树的最近公共祖先】 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 = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 后序遍历ans = Nonedef f(node) -> bool:# 返回是否有目标nonlocal ansif not node:return Falseleft = f(node.left)right = f(node.right)if left and right:# 左右子树有目标ans = nodereturn False    # 不需要再找，直接返回Falseif node is p or node is q:# 根节点为目标if left or right:# 左或右子树也有目标ans = nodereturn False# 左右无目标return Truereturn 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 = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 先序遍历if root is None or root is p or root is q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right:return rootif left:return leftreturn right

2.235. 二叉搜索树的最近公共祖先

（1）先序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 先序遍历if root is None or root is p or root is q:return rootleft = right = Nonemx, 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 rootif left:return leftreturn right

（2）先序优化，来自视频代码。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 先序优化# 不用判断当前节点是否为空，前提先序x = root.valif 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 root

2024.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, Nonel_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, nodeelse:return (l_h, l_node) if l_h > r_h else (r_h, r_node)_, ans = f(root, 0)return ans

2024.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 pathif node is None:return Falseif node.val == target:# 本节点不需要添加return Truepath.append("L")if dfs(node.left, target):return True# 左边没有path[-1] = "R"if dfs(node.right, target):return True# 右边没有path.pop()  #都没有，去掉当前路径return Falsepath = []dfs(root, startValue)pathToStart = pathpath = []dfs(root, destValue)pathToDest = pathwhile 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:returnnonlocal d, pathif 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 = 0n, m = len(d[startValue]), len(d[destValue])while i < n and i < m and d[startValue][i] == d[destValue][i]:i += 1return "U" * (n - i) + "".join(d[destValue][i:])

 完

感谢你看到这里！一起加油吧！

这篇关于2024.4.（22，23，28号）力扣刷题记录-二叉树学习记录4的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---