[leetcode]44 Balanced Binary Tree

タイトルリンク:https://leetcode.com/problems/balanced-binary-tree/ Runtimes:21ms
1、問題
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.
2、分析
まず,平衡二叉木とは何か,すなわち全ノードの左右のサブツリーの高さの差が2未満であることを理解することが平衡である.もともと非再帰的なものを使いたいと思っていましたが、書くのが面倒で、結局再帰を使いました.意外にも走ってしまいました.はは.
3、まとめ
実は再帰中に操作が少ない限り、time out、getの新しいスキルはありません.バランスツリーではないことをチェックしたら、そのまま戻ってきて、スピードが速い!
4、実現

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    int isBalanced(TreeNode *root, bool &f)
    {
        if(!f)
            return -1;
        if(root == NULL)
            return -1;
        int leftH, rightH;
        leftH = isBalanced(root->left, f) + 1;
        rightH = isBalanced(root->right, f) + 1;
        if(abs(leftH - rightH) > 1)
            f = false;
        return leftH < rightH ? rightH : leftH;
    }

    bool isBalanced(TreeNode *root) {
       bool f = true;
       isBalanced(root, f);
       if(f)
            return true;
        else
            return false;
    }
};

5、反省
簡単なテーマで、効果はいいです.