leetcode 검지 offer 두 갈래 나무 깊이
1571 단어 Java 기초---면접
제목:
두 갈래 나무의 뿌리 노드를 입력하여 이 나무의 깊이를 구하세요.뿌리 노드에서 잎 노드까지 순서대로 지나가는 노드(뿌리, 잎 노드 포함)는 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.
예:
두 갈래 나무[3,9,20,null,null,15,7],
3/\9 20/\15 7은 최대 깊이 3을 반환합니다.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.
사실 이 문제는 매우 간단하지만, 나의 데이터 구조는 많이 잊어버리지 않았다. 그리고 여기서 데이터 구조 두 갈래 나무의 지식을 회상해 보자
답안
public int maxDepth(TreeNode root) {
if(root==null) {
return 0;
}
int l=maxDepth(root.left);
int r=maxDepth(root.right);
return (l>r)?(l+1):(r+1);
}
이곳은 두 갈래 나무를 두루 돌아다니는 문제일 뿐이다.
그리고 앞 순서, 중간 순서, 뒤 순서를 회상해 보세요. 여기에 자바 코드를 첨부하세요.특히 간단한데, 차례대로 돌아가서 두 갈래 나무를 하나씩 찾는 것이다.
앞순서:
public void find(TreeNode root) {
//
if(root==null) {
return ;
}
System.out.println(root.data);
//
find(root.left);
find(root.right);
}
중간 순서:
public void find(TreeNode root) {
//
if(root==null) {
return ;
}
//
find(root.left);
System.out.println(root.data);
find(root.right);
}
후순:
public void find(TreeNode root) {
//
if(root==null) {
return ;
}
//
find(root.left);
find(root.right);
System.out.println(root.data);
}
아무튼 아주 간단해요.