leetcode543. Diameter of Binary Tree
1338 단어 leetcode자바binary-treerecursion
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example: Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
이 진 트 리 의 지름 은 한 잎 노드 에서 다른 잎 노드 까지 의 가장 먼 거 리 를 말 하 는데 이 거 리 는 두 노드 간 의 경로 가 길 다 는 것 을 말 하 는데 이 경 로 는 반드시 뿌리 노드 를 거치 지 않 는 다 는 것 을 주의해 야 한다.
아이디어 와 코드
여기 서 재 귀 를 통 해 계산 을 완성 할 수 있 습 니 다. 먼저 재 귀 를 통 해 왼쪽 서브 트 리 의 최대 높이 를 계산 한 다음 에 재 귀 를 통 해 오른쪽 서브 트 리 의 최대 높이 를 계산 하면 현재 노드 가 구성 할 수 있 는 가장 긴 경 로 를 얻 을 수 있 습 니 다.이 값 을 기록 해 야 합 니 다.재 귀적 으로 이 노드 의 최대 높이 를 외부 호출 자 에 게 운송 합 니 다.
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
heightOfBinaryTree(root);
return max;
}
public int heightOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
int left = heightOfBinaryTree(root.left);
int right = heightOfBinaryTree(root.right);
max = Math.max(left + right + 1, max);
return Math.max(left, right) + 1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.