Leet Code 매일 한 문제[69] 두 갈래 나무의 깊이
두 갈래 나무의 뿌리 노드를 입력하여 이 나무의 깊이를 구하세요.뿌리 노드에서 잎 노드까지 순서대로 지나가는 노드(뿌리, 잎 노드 포함)는 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof
예:
두 갈래 나무[3,9,20,null,null,15,7],3/\920/\157에게 최대 깊이 3을 되돌려줍니다.
팁:
노드 총 수<= 10000
제목 분석
해법
DFS 알고리즘은 이 트리의 깊이와 왼쪽(오른쪽) 하위 트리의 깊이 사이의 관계를 뒤따라 이동합니다.분명히 이 나무의 깊이는 왼쪽 나무의 깊이와 오른쪽 나무의 깊이의 최대치 +1과 같다
해법2
계층 정렬 BFS
코드 구현
public class TreeNodeMaxDepth {
public int maxDepth1(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList treeNodes = new LinkedList() {{
add(root);
}}, temp;
int res = 0;
while (!treeNodes.isEmpty()) {
temp = new LinkedList<>();
for (TreeNode treeNode : treeNodes) {
if (treeNode.left != null) {
temp.add(treeNode.left);
}
if (treeNode.right != null) {
temp.add(treeNode.right);
}
}
treeNodes = temp;
res++;
}
return res;
}
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
