이진 트리가 균형을 이루고 있는지 어떻게 알수있을까요?


학교에서 수업을 들은걸 겨울방학동안 복습해보고 있는데요. 이진트리를 공부하면서 궁금한게 생겼습니다. 트리의 높이가 균형이 맞는지를 알아내는 가장 좋은 방법이 뭔지 궁금합니다.

제생각에는

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //트리가 비었을때
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

이런식으로 하면 될것같은데 어떤가요? 뭐가 빠진게 있을까요?

  • 2016년 02월 23일에 작성됨

조회수 184


1 답변


좋아요
1
싫어요
채택취소하기

비슷하게 하신것같습니다.

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;
}

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

    if(Math.abs(left - right) > 1){
        return -1;
    }else{
        return 1 + Math.max(left, right);
    }
}

저는 이런식으로 해봤는데 참고해보세요.


로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close