제목:

1과 두 갈래 나무의 뿌리 결점을 입력하여 이 나무가 균형 두 갈래 나무인지 판단한다.만약 두 갈래 나무 중 임의로 결점된 좌우 자목의 깊이 차이가 1을 넘지 않는다면, 그것은 바로 균형 두 갈래 나무이다.

생각:

1. 반복 반복 결점
상기 문제를 참고하여 두 갈래 나무의 깊이를 구하고 뿌리 결점의 좌우 자목의 깊이를 구한 다음에 그들의 깊이의 차이가 1을 넘지 않는다고 판단한다. 그렇지 않으면 두 갈래 나무가 아니다.만약 그렇다면 같은 방법으로 왼쪽 나무와 오른쪽 나무가 균형 두 갈래 나무인지 아닌지를 판단하고, 만약 모두 그렇다면 이것이 바로 균형 두 갈래 나무다.
그러나 위의 방법은 자수가 균형 있는 두 갈래 나무인지 판단할 때 나무의 결점을 반복해서 자수의 깊이를 끊임없이 구하기 때문에 효율이 높지 않다.
2. 매듭점을 반복한다
우리는 결점을 두루 훑어보는 동시에 이 결점의 깊이를 기록함으로써 중복 방문을 피할 수 있다.

코드:

방법 1:

struct TreeNode{

    int val;

    TreeNode* left;

    TreeNode* right;

};



int TreeDepth(TreeNode* pRoot){

    if(pRoot==NULL)

        return 0;

    int left=TreeDepth(pRoot->left);

    int right=TreeDepth(pRoot->right);

    return left>right?(left+1):(right+1);

}



bool IsBalanced(TreeNode* pRoot){

    if(pRoot==NULL)

        return true;

    int left=TreeDepth(pRoot->left);

    int right=TreeDepth(pRoot->right);

    int diff=left-right;

    if(diff>1 || diff<-1)

        return false;

    return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);

}

방법 2:

bool IsBalanced_1(TreeNode* pRoot,int& depth){

    if(pRoot==NULL){

        depth=0;

        return true;

    }

    int left,right;

    int diff;

    if(IsBalanced_1(pRoot->left,left) && IsBalanced_1(pRoot->right,right)){

        diff=left-right;

        if(diff<=1 || diff>=-1){

            depth=left>right?left+1:right+1;

            return true;

        }

    }

    return false;

}



bool IsBalancedTree(TreeNode* pRoot){

    int depth=0;

    return IsBalanced_1(pRoot,depth);

}

온라인 테스트 OJ:

http://www.nowcoder.com/books/coding-interviews/8b3b95850edb4115918ecebdf1b4d222?rp=2
AC 코드:

class Solution {

public:

    bool IsBalanced_Solution(TreeNode* pRoot) {

		if(pRoot==NULL)

            return true;

        int left=TreeDepth(pRoot->left);

        int right=TreeDepth(pRoot->right);

        int diff=left-right;

        if(diff>1 || diff<-1)

            return false;

        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);

    }

    

    int TreeDepth(TreeNode* pRoot){

    	if(pRoot==NULL)

        	return 0;

    	int left=TreeDepth(pRoot->left);

    	int right=TreeDepth(pRoot->right);

    	return left>right?(left+1):(right+1);

	}

};

 

class Solution {

public:

    bool IsBalanced_Solution(TreeNode* pRoot) {

		int depth=0;

        return IsBalanced(pRoot,depth);

    }

    

    bool IsBalanced(TreeNode* pRoot,int& depth){

        if(pRoot==NULL){

            depth=0;

            return true;

        }

        int left,right,diff;

        if(IsBalanced(pRoot->left,left) && IsBalanced(pRoot->right,right)){

            diff=left-right;

            if(diff<=1 && diff>=-1){

                depth=left>right?left+1:right+1;

           		return true;

            }

        }

        return false;

    }

};