Leetcode563. 두 갈래 나무의 경사도
Leetcode563. 두 갈래 나무의 경사도
제목: 두 갈래 나무를 정해 전체 나무의 경사도를 계산한다.하나의 트리의 노드의 경사도 정의는 이 노드의 왼쪽 트리의 결점과 오른쪽 트리의 결점의 합차의 절대값이다.빈 결점의 경사도는 0이다.전체 나무의 경사는 모든 노드의 경사의 합이다. :
:
1
/ \
2 3
:1
:
2 : 0
3 : 0
1 : |2-3| = 1
: 0 + 0 + 1 = 1
문제:
:
:
1
/ \
2 3
:1
:
2 : 0
3 : 0
1 : |2-3| = 1
: 0 + 0 + 1 = 1
/**
* @param root
* @return
*/
public static int findTilt(TreeNode root) {
int sum = 0;
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int s1 = 0, s2 = 0;
if (node.left != null) {
s1 = node.left.value;
queue.add(node.left);
}
if (node.right != null) {
s2 = node.right.value;
queue.add(node.right);
}
int tmp = Math.abs(s1 - s2);
sum += tmp;
}
return sum;
}
static int tilt;
/**
*
* @param root
* @return
*/
public static int findTilt2(TreeNode root) {
if (root == null) return 0;
int leftSum = findTilt2(root.left);
int rightSum = findTilt2(root.right);
tilt += Math.abs(leftSum - rightSum);
return leftSum + rightSum + root.value;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.