力扣每日练习（3.16）补

本文主要是介绍力扣每日练习（3.16）补，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

124. 二叉树中的最大路径和

路径和 是路径中各节点值的总和。不要求一定走根节点。
使用递归。
可以先从上到下观察，二叉树是由一个根节点和左右子树组成的。
假设根节点和左右子树的最大贡献的和是最大路径和，那么这个左右子树的最大贡献都是大于等于0的。
再往下走，左子树的根节点就要和其左右子树的最大贡献求和，看是不是全局的最大路径和；同时为了向上一层根节点提供左子树的最大贡献，也必须比较出左子树的左右子树中贡献最大的那个，加上左子树的根节点，就是左子树的最大贡献。右子树同理。
就这样不断往下分解问题，在中间的每一层都要计算下一层的贡献，到了叶节点，就返回贡献是它自身，在逐层往上返回，得到最终结果。

解题思路：
需要一个全局变量max_num记录最大路径和；
需要设计递归的结束条件，当节点是叶子节点，其左右子树贡献均为0；
递归主体：遇见一个节点，需要知道其左右子树的贡献，也就是递归遍历其左右子树；得到左右子树的分别的贡献后，先尝试计算以当前节点为根节点，加上左右子树的贡献的路径和，更新最大路径和；再往上看，需要和父节点一起，自己充当子树的贡献，也就是自己要返回自己加左子树或者右子树当中最大贡献的那个，作为子树贡献向父节点服务。

# 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 n
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:def dfs(node):nonlocal max_sum # 表示全局变量# 终止条件，叶子节点的左右子树都为空if not node: return 0# 递归主体，计算左右子树的贡献，如果为负，则要置为0，求的最大值left_gain = max(dfs(node.left),0) # 左子树right_gain = max(dfs(node.right),0) # 右子树# 递完成后，开始归，看看当前节点为根节点的话是不是左右子树加自己最大current_path = node.val + left_gain + right_gainmax_sum = max(max_sum, current_path) # 更新最大路径和# 还要考虑往上的父节点，自己作为子树的贡献return node.val + max(left_gain, right_gain)# 定义最大路径和max_sum = float('-inf')# 从根节点开始递dfs(root)return max_sum

1. 如何思考二叉树相关问题？
   • 不要一开始就陷入细节，而是思考整棵树与其左右子树的关系。
2. 为什么需要使用递归？
   • 子问题和原问题是相似的，他们执行的代码也是相同的（类比循环），但是子问题需要把计算结果返回给上一级，这更适合用递归实现。
3. 为什么这样写就一定能算出正确答案？
   • 由于子问题的规模比原问题小，不断“递”下去，总会有个尽头，即递归的边界条件 ( base case )，直接返回它的答案“归”；
   • 类似于数学归纳法（多米诺骨牌），n=1时类似边界条件；n=m时类似往后任意一个节点
4. 计算机是怎么执行递归的？
   • 当程序执行“递”动作时，计算机使用栈保存这个发出“递”动作的对象，程序不断“递”，计算机不断压栈，直到边界时，程序发生“归”动作，正好将执行的答案“归”给栈顶元素，随后程序不断“归”，计算机不断出栈，直到返回原问题的答案，栈空。
5. 另一种递归思路
   • 维护全局变量，使用二叉树遍历函数，不断更新全局变量最大值。

199. 二叉树的右视图

解题思路：也就是找每一层的最右边的节点元素，直接层序遍历，只添加每层最右边的节点到结果

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:if not root:return []queue = [root]  # 使用列表作为队列res = []while queue:level_length = len(queue)  # 当前层的节点数量for i in range(level_length):node = queue.pop(0)  # 从列表的开始移除元素，模拟队列行为if i == level_length - 1:  # 如果是当前层的最后一个节点res.append(node.val)  # 添加到结果中if node.left:  # 如果有左子节点，加入队列queue.append(node.left)if node.right:  # 如果有右子节点，加入队列queue.append(node.right)return res

226. 翻转二叉树

解题思路：递归的做法，针对每一个二叉树子树，我们都交换左右节点，如果当前节点不存在，就返回null

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:def dfs(node):# 终止条件，节点为空if not node: return None# 交换当前子树的左右节点node.left, node.right = node.right, node.left# 针对左子树dfs(node.left)# 针对右子树dfs(node.right)dfs(root)# 返回根节点return root

也可以使用栈的做法，从根节点开始，新增节点，并交换这些节点的左右子节点

class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: returnstack = [root]while stack:node = stack.pop()if node.left: stack.append(node.left)if node.right: stack.append(node.right)node.left, node.right = node.right, node.leftreturn root

这篇关于力扣每日练习（3.16）补的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---