[이 진 트 리] 밸 런 스 이 진 트 리.

4075 단어 데이터 구조
밸 런 스 이 진 트 리 (AVL)
특성
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);
}

좋은 웹페이지 즐겨찾기