두 갈래 트리 경로와 문제
2355 단어 두 갈래 나무
문제 설명:
비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.
본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.
대체적인 사고방식:
최대 경로 및 다음 네 가지 가능성이 있습니다.
1) 현재 결점의 왼쪽 하위 트리 결점에서 오른쪽 하위 트리 결점까지
2) 현재 끝점에서 왼쪽 하위 트리 노드로
3) 현재 끝점에서 오른쪽 하위 트리 노드로
4) 현재 결점 자체
가능성을 분석한 결과 현재 결점의 최대 경로와 하위 노드가 상황인 경우 부모 노드가 하위 결점을 얻는 경로와 아무런 작용이 없다는 것을 발견했다.따라서 우리는 전역 변수를 사용하여 최대 경로를 저장하고 이 노드로 출발하는 최대 경로 (약간 두 갈래 나무의 깊이와 유사) 를 반복적으로 되돌려줍니다. 임의의 결점이 임의의 노드로 출발하기 때문에 현재 결점의 최대 경로가 0보다 작을 때 되돌아오는 값은 0이어야 합니다.
구현 코드는 다음과 같습니다.
class Solution {
int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
process(root);
return ans;
}
public int process(TreeNode root){ // root
if(root == null){
return 0;
}
int left = process(root.left);
int right = process(root.right);
ans = Math.max(ans, root.val + left + right);
return Math.max(0, Math.max(root.val + right, root.val + left));
}
}문제 2: 최대 동일 값 경로(leetcode687)
문제 설명:
두 갈래 트리를 지정해서 가장 긴 경로를 찾으십시오. 이 경로의 모든 노드는 같은 값을 가지고 있습니다.이 경로는 통과할 수도 있고 루트 노드를 통과하지 않을 수도 있다.
참고: 두 노드 사이의 경로 길이는 둘 사이의 모서리로 표시됩니다.
대체적인 사고방식:
모두 경로와 문제이기 때문에 문제 1의 네 가지 가능성과 같다.
글로벌 변수를 사용하여 가장 큰 동일 경로 및 를 저장합니다.
현재 결점으로 출발하는 최대 동치 경로와length를 반복해서 되돌려줍니다.
현재 노드가 좌우 아이의length를 받을 때 좌우 아이가 현재 결점치와 같은지 판단할 수 있다. 만약에 같은length가 좌우 아이 중 길이가 가장 큰 가1이다.현재 결점을 통과하는 최대 경로 길이는 좌우 아이의 길이 + 1의 합입니다.
구현 코드는 다음과 같습니다.
class Solution {
public int ans = 0;
public int longestUnivaluePath(TreeNode root) {
process(root);
return ans;
}
public int process(TreeNode root){ //
if(root == null){
return 0;
}
int sum = 0;//
int length = 0; //
int left = process(root.left);
int right = process(root.right);
if(root.left != null && root.val == root.left.val){
sum += left + 1;
length = left + 1;
}
if(root.right != null && root.val == root.right.val){
sum += right + 1;
length = Math.max(length, right + 1);
}
ans = Math.max(ans, sum);
return length;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
