110. Balanced Binary Tree

110. Balanced Binary Tree
Total Accepted: 100175 
Total Submissions: 298232 
Difficulty: Easy
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of 
the two subtrees of every node never differ by more than 1.
Subscribe to see which companies asked this question
Hide Tags
 
Tree Depth-first Search
Hide Similar Problems
 
(E) Maximum Depth of Binary Tree
分析:
以下は間違いの答えです.201/226ケースをクリア!

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* node) 
    {
        if(node==NULL)
            return 0;
        return 1+max(maxDepth(node->left),maxDepth(node->right));
    }
    bool isBalanced(TreeNode* root) {
        if(root==NULL)
            return true;
        if(abs(maxDepth(root->left) - maxDepth(root->right)) > 1)//                    1
            return false;
        return true;    
    }
};

コードを修正した後(注意、依然としてエラー):ケースを通して、218/226
今度はどこが間違っているのか分からない!

class Solution {
public:
    int maxDepth(TreeNode* node) 
    {
        if(node==NULL)
            return 0;
        return 1+max(maxDepth(node->left),maxDepth(node->right));
    }
    int minDepth(TreeNode* node) 
    {
        if(node==NULL)
            return 0;
        return 1+min(minDepth(node->left),minDepth(node->right));
    }
    bool isBalanced(TreeNode* root) {
        if(root==NULL)
            return true;
        int maxleft  = maxDepth(root->left);
        int maxright = maxDepth(root->right);
        int minright = minDepth(root->right);    
        int minleft  = minDepth(root->left);
        if(abs(maxleft-minright) > 1)//       1
            return false;
        if(abs(maxright-minleft) > 1)//       1
            return false;    
        if(abs(maxleft-minleft) > 1)//       1
            return false;
        if(abs(maxright-minleft) > 1)//       1
            return false;
        return true;    
    }
};

他の人の分析を参考にします.
标题:一本の二叉木を与えて、高さのバランスが取れているかどうかを判断する.高さのバランスとは,各ノードに対して左サブツリーと右サブツリーの高さが最大1ずつ異なることを意味する.構想:まず高さを求める関数を書き、そのノードの高さを再帰的に求め、height(root)=1+max(height(root->left)、height(rootright->right))を求める.次に、高さのバランスがとれているかどうかを再帰的に判断し、現在のノードの左サブツリーの右サブツリーの高さの差が1未満である場合、左子と右子が高さのバランスを満たしているかどうかを再帰的に判断します.以上です.コードは次のとおりです.

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL)return true;
        int diff = depth(root->left) - depth(root->right);
        if( diff >= -1 && diff <= 1) return isBalanced(root->left) && isBalanced(root->right);
        else return false;
    }
    int depth(TreeNode* root){
        if(root == NULL)  return 0;
        else  return max(depth(root->left),depth(root->right)) + 1;
    }
};

以上のコードは同じノードに対して何度も高さを求めるが,アルゴリズムの複雑さはn個のノードを遍歴する必要があり,各ノードの高さを求めるにはlg(n)の高さを平均的に探索する必要があるため,複雑度はO(nlgn)である.したがって,各ノードに対して1回の高さだけを求めるべきであり,明らかに再帰的には下のノードから上へ,上のノードの高さは下のノードの高さに依存する結果である.ルートノードの高さを求めるときは、左右の子供の高さを再帰的に求め、その中の大きな値に1を加算します.実は左右の子どもの高さを求める場合、左右の子の木がバランスしているかどうかを判断することができ、バランスがとれていなければ戻り高さ値は-1が子の木がバランスしていないことを表すので、バランスではないので、再帰はすぐに実行を停止し、上へ-1を返し続けます.左右のサブツリーがバランスしている場合は、左右のサブツリーの差を確認します.これにより、ノードの高さを繰り返し計算する必要はありません.以上です.コードは次のとおりです.

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL)return true;
        return (checkHeight(root) > 0);
    }
    int checkHeight(TreeNode* root) {
        if(root == NULL)  return 0;
        int left = checkHeight(root->left);
        if(left == -1)  return -1;
        int right = checkHeight(root->right);
        if(right == -1)  return -1;
        int diff = left - right;
        if(diff > 1 || diff < -1)  return -1;
        return max(left, right) + 1;
    }

};

注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/50811950
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895
リファレンスリソース:
【1】ブログアドレス、http://blog.csdn.net/u014673347/article/details/46707609