검지 Offer 응답 흐름 시리즈 - 두 갈래 나무의 깊이

1477 단어

면접 문제 55: 두 갈래 나무의 깊이


제목 설명


문제 (1) 두 갈래 나무의 깊이
두 갈래 나무의 뿌리 결점을 입력하여 이 나무의 깊이를 구하세요.뿌리 결점에서 잎 결점까지 순서대로 지나가는/결점(뿌리, 잎 결점 포함)은 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다.
문제 (2) 균형 트리
두 갈래 나무의 뿌리 결점을 입력하여 이 나무가 균형 잡힌 두 갈래 나무인지 판단한다.만약 어떤 두 갈래 나무 중 임의로 결점된 좌우 자목의 깊이 차이가 1을 넘지 않는다면, 그것은 바로 균형 두 갈래 나무이다.

문제 분석


문제 (1) 분석
첫 번째 문제는 모두에게 작은 뜻입니다. 나무의 깊이=max(왼쪽 나무 깊이, 오른쪽 나무 깊이)+1, 귀속을 통해 실현됩니다.
문제 (2) 분석
트리의 깊이를 계산해야 합니다. 트리의 깊이=max(왼쪽 트리 깊이, 오른쪽 트리 깊이)+1.
반복하는 과정에서 좌우 자목의 깊이 차이가 1을 초과하는지 판단해야 한다. 만약 균형이 맞지 않으면 나무의 깊이를 =-1로 한다.최종적으로 나무의 깊이가 -1인지 여부에 따라 이 나무가 균형 나무인지 아닌지를 확정한다.

문제 해결


질문 (1)
     public int TreeDepth(Node root) {
        if(root==null) {
            return 0;
        }
        int left=TreeDepth(root.left);
        int right=TreeDepth(root.right);
        return Math.max(left+1,right+1);
    }

질문 (2)
    //  
    public boolean IsBalanced_Solution(Node root) {
        return getDepth(root)!=-1;
    }

    public int getDepth(Node 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);
    }
leetcode337. House Robber III
[USACO 2.3.2] 젖소 가보.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage