[LeetCode]110.Balanced Binary Tree

【题目】

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.

【分析】

无

【代码】

/*********************************
*   日期：2014-12-24
*   作者：SJF0115
*   题目: 110.Balanced Binary Tree
*   来源：https://oj.leetcode.com/problems/balanced-binary-tree/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if(balancedHeight(root) == -1){
            return false;
        }
        else{
            return true;
        }//if
    }
private:
    // 如果是平衡二叉树返回该二叉树的高度
    // 否则返回-1
    int balancedHeight(TreeNode *node){
        if(node == NULL){
            return 0;
        }//if
        // 左子树高度
        int left = balancedHeight(node->left);
        // 右子树高度
        int right = balancedHeight(node->right);
        // 左右子树高度差不超过1
        if(abs(left - right) > 1 || left < 0 || right < 0){
            // -1代表不满足平衡二叉树要求
            return -1;
        }//if
        return max(left,right)+1;
    }
};

//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){
    int data;
    //按先序次序输入二叉树中结点的值,-1表示空树
    cin>>data;
    if(data == -1){
        T = NULL;
    }
    else{
        T = new TreeNode(data);
        //构造左子树
        CreateBTree(T->left);
        //构造右子树
        CreateBTree(T->right);
    }
    return 0;
}

int main() {
    Solution solution;
    TreeNode* root(0);
    CreateBTree(root);
    cout<<solution.isBalanced(root);
}

【复杂度】

时间复杂度 O(n)，空间复杂度 O(logn)