[Leet Code] 124번: 두 갈래 나무의 최대 경로와
본고는 좌신 알고리즘 중의 두 갈래 나무 중의 가장 먼 거리를 비교할 수 있다. 단지 가장 먼 거리에서 권중을 고려하지 않은 문제일 뿐이다. 본고는 각 노드의 권중을 고려해야 하는데 차이가 있다.
제목: 비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.
본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.
예 1:
입력: [1,2,3]
1 / \ 2 3
출력: 6 예 2:
입력: [-10,9,20,null,null,15,7]
-10 / \ 9 20 / \ 15 7
출력: 42
제목에 따라 최대 경로는 왼쪽 트리, 오른쪽 트리, 루트 노드와 왼쪽 트리에 나타날 수 있습니다.우리의 사고방식은bottom에서topreturn으로 돌아가는 과정에서 왼쪽 트리와 오른쪽 트리의 경로가 더 큰 것을 기록하고 부모 노드에 현재 노드와 하위 트리로 구성된 최대치를 제공하는 것이다.
반복 설계:
1. 반환값: (root.val) + max(left,right) 즉 이 노드와 좌우 트리의 최대 값의 합으로 비교적 나쁜 해답은 버려지고 더 이상 사용되지 않습니다.
2. 귀속 중지 조건: 잎 노드를 넘어 0으로 돌아간다.
3. 레코드 최대값: 현재 노드 최대값 = root.val + left + right.
4. 최종적으로 모든 경로의 전역 최대치를 되돌려주면 된다
public class MaxPathSum_124 {
public class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
// maxSum
private int maxSum = Integer.MIN_VALUE;
private int maxPathSum(TreeNode root){
maxPath(root);
return maxSum;
}
private int maxPath(TreeNode root){
if(root == null){
// 0
return 0;
}
int left = maxPath(root.left);
int right = maxPath(root.right);
maxSum = Math.max(left + right + root.val, maxSum);
int temp = Math.max(left, right) + root.val;
return temp > 0 ? temp : 0;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
