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

조회수 1282회

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

제생각에는

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;
}

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

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);
        }
    }
    

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

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)