두 갈래 나무의 깊이에 관한 문제
1842 단어 평형수두 갈래 나무 깊이검지offer
제목
두 갈래 나무의 뿌리 노드를 입력하여 이 나무의 깊이를 구하세요.루트 노드에서 잎 노드까지 순서대로 지나가는 결점은 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.
생각
제목을 간소화하고 한 노드를 생각할 때 두 갈래 나무의 깊이는 1이다. 왜냐하면 좌우 나무가 모두 0이기 때문이다.
두 노드의 경우 두 갈래 나무의 깊이는 2이고 좌우 자목의 깊이는 최대치에 1을 더한다.
3개의 노드는 두 가지 상황으로 나뉩니다.
4 3
/ \ \
3 5 4
\
5
우리는 이 두 가지 상황을 통해 알 수 있듯이, 임의의 두 갈래 나무의 깊이가 바로 그것의 좌우자 나무의 깊이의 최대치 더하기 1이다
첫 번째: 3, 5의 깊이는 모두 1이기 때문에 4의 깊이는 2이다
두 번째: 5의 깊이는 1, 4의 깊이는 2, 3의 깊이는 3이다
.....
코드는 다음과 같습니다.
public static int getDeep(BinaryTree root )
{
if(root==null)
{
return 0;
}
int nleft = getDeep(root.left);
int nright = getDeep(root.right);
return nleft > nright ? nleft+1 : nright +1;
}뻗다
어떻게 한 그루의 두 갈래 나무를 균형 두 갈래 나무로 판단하는가(임의의 노드의 좌우 자목의 깊이 차이는 1을 초과하지 않는다).
우리는 위의 사상을 빌려 다음과 같은 코드를 실현할 수 있다.
public static boolean isBalanced(BinaryTree root) {
if(root == null)return true;
int in = getDeep1(root);
if(in >= 0)
return true;
else
return false;
}
public static int getDeep(BinaryTree root )
{
if(root==null)
{
return 0;
}
int nleft = getDeep(root.left);
int nright = getDeep(root.right);
//System.out.println("root:"+root.value);
//System.out.println("left:"+nleft);
//System.out.println("right:"+nright);
if(nright <0 || nleft < 0) return -1; // 0， 1 ，
if(Math.abs(nleft-nright) >1)return -1; // 1， -1
return nleft > nright ? nleft+1 : nright +1; //
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이에 관한 문제제목 두 갈래 나무의 뿌리 노드를 입력하여 이 나무의 깊이를 구하세요.루트 노드에서 잎 노드까지 순서대로 지나가는 결점은 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다. 생각 제목을 간소화하고 한 노...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
