[LeetCode] 124. Binary Tree Maximum Path Sum
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42두 번째 예를 주의하십시오. 노드 값은 음수가 존재할 것입니다.사고방식은 뒷걸음질입니다. 경로와 항상 왼쪽 아이 val + 오른쪽 아이 val + 현재 노드 val을 포함해야 하기 때문입니다.방법은 다른 뒷순서로 훑어보는 문제와 거의 같고 전체 변수를 만들어 마지막 결과를 기록하는 것이다.helper 함수에서 왼쪽 트리와 오른쪽 트리를 귀속할 때 0과 누가 큰지 기억합니다. 노드 값은 음수를 포함하기 때문입니다.res는 루트입니다.val + left + right.
시간 O(n)
공간 O(n)
Java 구현
1 class Solution {
2 int res;
3
4 public int maxPathSum(TreeNode root) {
5 // corner case
6 if (root == null) {
7 return 0;
8 }
9 res = Integer.MIN_VALUE;
10 helper(root);
11 return res;
12 }
13
14 public int helper(TreeNode root) {
15 if (root == null) {
16 return 0;
17 }
18 int left = Math.max(0, helper(root.left));
19 int right = Math.max(0, helper(root.right));
20 res = Math.max(res, left + right + root.val);
21 return Math.max(left, right) + root.val;
22 }
23 }JavaScript 구현
1 /**
2 * @param {TreeNode} root
3 * @return {number}
4 */
5 var maxPathSum = function (root) {
6 let res = -Infinity;
7 let helper = function (root) {
8 if (root == null) return 0;
9 let left = Math.max(0, helper(root.left));
10 let right = Math.max(0, helper(root.right));
11 // let newPath = root.val + left + right;
12 res = Math.max(root.val + left + right, res);
13 return Math.max(left, right) + root.val;
14 }
15 helper(root);
16 return res;
17 };이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
