# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
# 定義一個數字存放最大的路徑和
self.max_sum = float("-inf")
def dfs(root):
# 當節點為空的時候回傳零
if not root:return 0
# 遞回左子樹和右子樹，并接識訓傳值
left = dfs(root.left)
right = dfs(root.right)
# self.max_sum必然是left或者right的子樹的路徑，
# 因此這里判斷是否需要經過根節點
self.max_sum = max(self.max_sum,left + right + root.val)
# 這里不針對根節點，對于根節點的兒子節點來說，
# 路徑只能包含兒子節點中的一個
return max(0,max(left,right) + root.val)
dfs(root)
return self.max_sum
A = Solution()
print(A.maxPathSum(a))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/98255.html
標籤：Python
上一篇：[MySQL] 使用force index強制使用索引
下一篇：Python必須知道的例外處理