48、路径总和III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
- 二叉树的节点个数的范围是
[0,1000] -109 <= Node.val <= 109-1000 <= targetSum <= 1000
思路解答：
1、定义一个递归函数 dfs(node, target)，表示从当前节点 node 开始，路径和为 target 的路径数目。
2、在递归函数中，首先检查当前节点是否为空，如果是空节点则直接返回 0。
3、然后，检查以当前节点为起点的路径中是否存在满足条件的路径，如果存在，则路径数目加 1。
4、递归地调用 dfs 函数计算左子树和右子树中满足条件的路径数目，并将二者之和返回。
5、主函数中调用以根节点开始的路径数量与左、右子树的路径数量之和相加，返回总路径数量作为结果。
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
def dfs(node, target):
if not node:
return 0
count = 0
if node.val == target:
count += 1
count += dfs(node.left, target - node.val)
count += dfs(node.right, target - node.val)
return count
if not root:
return 0
return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum)
49、二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
思路解答：
1、从根节点开始递归遍历二叉树。
2、如果当前节点为null或者等于其中一个目标节点，则返回当前节点。
3、递归地在左子树和右子树中查找目标节点。
4、如果左子树和右子树均找到目标节点，则当前节点即为最近公共祖先。
5、如果只在一侧找到目标节点，则返回找到的节点作为最近公共祖先。
def lowestCommonAncestor(self, root: Optional[TreeNode], p: Optional[TreeNode], q: Optional[TreeNode]) -> Optional[TreeNode]:
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
elif left:
return left
else:
return right
50、二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
思路解答：
- 递归计算最大路径和：通过深度优先搜索（DFS）的方式递归地计算每个节点作为路径中的根节点时的最大路径和。
- 最大贡献值计算：对于每个节点，计算其左子树和右子树的最大贡献值。如果子树的最大贡献值为负数，则取0，因为负数对路径和没有贡献。
- 当前节点路径和计算：根据当前节点的值以及左子树和右子树的最大贡献值，计算当前节点作为路径中的根节点时的最大路径和。这包括当前节点值、左子树路径和、右子树路径和，以及同时经过左子树和右子树的路径和。
- 更新全局最大路径和：在每个节点处，将当前节点作为路径中的根节点时的最大路径和与全局最大路径和进行比较，更新全局最大路径和为较大值。
- 返回最大贡献值：在递归的过程中，每个节点返回的是以该节点为路径中的一部分时的最大贡献值，这个值用于计算父节点的最大路径和。
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.max_sum = float('-inf')
def max_path(node):
if not node:
return 0
left_sum = max(max_path(node.left), 0)
right_sum = max(max_path(node.right), 0)
# 当前节点作为路径中的根节点时的最大路径和
current_path_sum = node.val + left_sum + right_sum
self.max_sum = max(self.max_sum, current_path_sum)
# 返回当前节点的最大路径和
return node.val + max(left_sum, right_sum)
max_path(root)
