[이 진 트 리] 밸 런 스 이 진 트 리.
4075 단어 데이터 구조
특성
1. 좌우 나무 깊이 의 차이 (균형 인자) 의 절대 치 는 12 를 초과 하지 않 습 니 다. 좌우 나무 도 모두 균형 이 진 트 리 입 니 다. 빈 나무 나 상기 두 가지 성질 을 가 진 나무 입 니 다.또한 이 진 트 리, 이 진 트 리 를 찾 아야 합 니 다.
프로 그래 밍 문제
【 1 】 이 진 트 리 한 그루 를 입력 하여 이 이 진 트 리 가 균형 이 잡 힌 이 진 트 리 인지 판단 합 니 다.
- 재 귀 방법 - 아래 에서 위로 옮 겨 다 니 며 각 노드 는 한 번 만 옮 겨 다 니 며 한 노드 에 옮 겨 다 닐 때 좌우 자 나 무 는 이미 옮 겨 다 녔 다. 만약 에 자 나 무 는 균형 이 잡 힌 이 진 트 리 라면 자 나무의 깊이 로 돌아간다.하위 트 리 가 균형 이 잡 힌 이 진 트 리 가 아니라면 옮 겨 다 니 는 것 을 중단 합 니 다.
위 에서 아래로 옮 겨 다 니 면 상층 의 결점 을 판단 할 때 하층 의 결점 을 여러 번 반복 하여 불필요 한 지출 을 증가 시킨다.
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
private int getDepth(TreeNode root){
if (root == null)
return 0;
int left = getDepth(root.left);
if (left == -1)
return -1;// ,
int right = getDepth(root.right);
if (right == -1)
return -1;
return Math.abs(left-right)>1 ? -1:1+Math.max(left,right);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.