124. 二叉树中的最大路径和 - 力扣（LeetCode）

K1 defination of Path

if you write a sequence composed of nodes in a binary tree like 1 -> 2 -> 3, it should:

1. nodes before and after -> should be father-son in the binary tree

2. A node can only appear in the sequence at most once

so you have a tree like this:

5

/ \

3 4

/ \

6 7

to include all the nodes in the tree into ans is illeagel, beacuse the path will be:

6 → 3 → 7 → 3 → 5 → 4

↑

重复了!

although it obey principle1

so our ans is compose by a diameter at most.

K2: look 0x3f Q-A

124. 二叉树中的最大路径和 - 力扣（LeetCode）

K3:if you return 0, means you didn't want to add this path into ans

ans = max(ans, root.val + left_val + right_val)

this doesn't mean ans must a diameter

Q1: will this solution take at least one leaf into ans?

No, this is because you didn't read the code carefally

return max(max(left_val, right_val) + root.val ,0)

on the right there is a 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
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf
        # return the max link path sum of a tree
        def dfs(root):
            if root is None:
                return 0 # return 0 equals to not include this node
            left_val = dfs(root.left)
            right_val = dfs(root.right) # left_val,right_val >= 0
            nonlocal ans
            ans = max(ans, root.val + left_val + right_val)
            return max(max(left_val, right_val) + root.val ,0)
        dfs(root)
        return ans