LeetCode: The Difference between LeetCode 104 and LeetCode 124

Problem Statement: 104 Maximum Depth of Binary Tree

104 Maximum Depth of Binary Tree:
Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

问题陈述: 104 二叉树的最大深度
给定一个二叉树的根节点，返回其最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数量。

Problem Statement: 124 Binary Tree Maximum Path Sum

124 Binary Tree Maximum Path Sum:
Given the root of a binary tree, return the maximum path sum. A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. The path does not need to pass through the root.

问题陈述: 124 二叉树的最大路径和
给定一个二叉树的根节点，返回最大路径和。二叉树中的路径是一系列节点，其中序列中每对相邻节点都有一条连接它们的边。一个节点在序列中最多只能出现一次。路径不需要通过根节点。

Key Differences / 关键区别

1. Definition of "Depth" vs "Path Sum"

Maximum Depth (104): This is a measure of how deep the tree goes, counting the number of nodes along the longest path from the root to a leaf.
Maximum Path Sum (124): This is a measure of the highest sum of values along any path in the tree. The path can start and end at any node, not necessarily the root or a leaf.

1. “深度”与“路径和”的定义

最大深度 (104): 这是树的深度，从根到叶节点的最长路径上的节点数量。
最大路径和 (124): 这是树中任意路径上的值的最大和。路径可以从任何节点开始并结束，不一定是根或叶节点。

2. Nature of the Problem

Maximum Depth is a structural property of the tree.
Maximum Path Sum is a property based on the values of the nodes and the possible paths.

2. 问题的性质

最大深度 是树的结构属性。
最大路径和 是基于节点值和可能路径的属性。

3. Approach Differences

Maximum Depth (104): Typically solved using DFS or BFS to traverse the tree and count the depth.
Maximum Path Sum (124): Solved using DFS with additional logic to keep track of the path sums and to manage the inclusion/exclusion of node values based on whether including the node maximizes the sum.

3. 方法的不同

最大深度 (104): 通常使用DFS或BFS遍历树并计算深度。
最大路径和 (124): 使用DFS并添加逻辑来跟踪路径和，根据是否包括节点以最大化和来管理节点值的包含/排除。

Example and Solution Comparison / 示例和解决方案比较

104 Maximum Depth of Binary Tree

Example:

Input: root = [3,9,20,null,null,15,7]
Output: 3

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return max(left_depth, right_depth) + 1

124 Binary Tree Maximum Path Sum

Example:

Input: root = [1,2,3]
Output: 6

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def helper(node):
            nonlocal max_sum
            if not node:
                return 0
            left_max = max(helper(node.left), 0)
            right_max = max(helper(node.right), 0)
            current_max = node.val + left_max + right_max
            max_sum = max(max_sum, current_max)
            return node.val + max(left_max, right_max)

        max_sum = float('-inf')
        helper(root)
        return max_sum

Complexity Analysis Comparison / 复杂度分析比较

Time Complexity:

104 Maximum Depth of Binary Tree: O(n), where n is the number of nodes in the tree.
124 Binary Tree Maximum Path Sum: O(n), where n is the number of nodes in the tree.

时间复杂度:

104 二叉树的最大深度: O(n)，其中n是树中的节点数。
124 二叉树的最大路径和: O(n)，其中n是树中的节点数。

Space Complexity:

104 Maximum Depth of Binary Tree: O(h), where h is the height of the tree due to the recursion stack.
124 Binary Tree Maximum Path Sum: O(h), where h is the height of the tree due to the recursion stack.

空间复杂度:

104 二叉树的最大深度: O(h)，其中h是树的高度，原因是递归栈。
124 二叉树的最大路径和: O(h)，其中h是树的高度，原因是递归栈。

Key Concept / 关键概念

104 Maximum Depth of Binary Tree: Recursion and tree traversal techniques (DFS/BFS).
124 Binary Tree Maximum Path Sum: Recursion, tree traversal, and dynamic programming to keep track of the maximum path sum.

关键概念:

104 二叉树的最大深度: 递归和树遍历技术（DFS/BFS）。
124 二叉树的最大路径和: 递归、树遍历和动态编程来跟踪最大路径和。

Tips / 提示

For 104, focus on understanding tree traversal methods.
For 124, focus on combining traversal methods with dynamic programming concepts.

提示:

对于104，重点理解树遍历方法。
对于124，重点将遍历方法与动态编程概念结合。

Solution Template for similar questions / 提示

104: Similar questions include problems involving finding the depth, height, or level order traversal of trees.
124: Similar questions include problems involving finding path sums, maximum sums, or longest paths in trees.

相似问题的解决方案模板

104: 类似问题包括涉及找到树的深度、高度或层次遍历的问题。
124: 类似问题包括涉及找到树中的路径和、最大和或最长路径的问题。

CODEBITWAVE