[Leetcode] 0124. 二分木最大パス合計

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

あパスバイナリツリーでは、シーケンス内の隣接するノードの各ペアに、それらを接続するエッジがあるノードのシーケンスです。ノードはシーケンス内にのみ出現できる 最大1回。パスはルートを通過する必要がないことに注意してください。

の パス合計 パスの合計は、パス内のノードの値の合計です。

与えられた 根 バイナリツリーの戻り値 最大限 パス合計 いずれの 空でない パス.

例 1:

入力： ルート = [1,2,3]
出力： 6
説明： 最適なパスは 2 -> 1 -> 3 で、パスの合計は 2 + 1 + 3 = 6 になります。

例 2:

入力： ルート = [-10,9,20,null,null,15,7]
出力： 42
説明： 最適なパスは 15 -> 20 -> 7 で、パスの合計は 15 + 20 + 7 = 42 になります。

制約:

ツリー内のノードの数は範囲内です [1, 3 * 10 ⁴ ].
-1000 <= ノード値 <= 1000

パイソン

				
					# 時間計算量: O(n) # 空間計算量: O(n) 入力から Optional クラス TreeNode をインポート: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right クラス ソリューション: def maxPathSum(self, root: Optional[TreeNode]) -> int: maxPath = float('-inf') def dfs(node: Optional[TreeNode]): nonlocal maxPath if node is None: return 0 pathLeft = max(dfs(node.left), 0) pathRight = max(dfs(node.right), 0) maxPath = max(maxPath, pathLeft + pathRight + node.val) return max(pathLeft + node.val, pathRight + node.val) dfs(root) return maxPath root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) print(Solution().maxPathSum(root))

パイソン

関連記事