题目描述
给定一个二叉树,判定其是否是平衡二叉树
样例
输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示,
5
/ \
7 11
/ \
12 9
输出:true
C代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
//本题用求树的深度思路来做
bool flag = true;
int maxHigh(int a,int b){
if(a >= b)
return a;
else
return b;
}
//求树高
int TreeDeepth(struct TreeNode *root){
if(!root)
return 0;
int leftHigh = TreeDeepth(root->left);//递归左子树求左子树的高度
int rightHigh = TreeDeepth(root->right);//递归右子树求右子树的高度
if(abs(leftHigh - rightHigh) > 1)//如果左右子树的高度差的绝对值大于1了表示其不是一颗平衡二叉树了
flag = false;
else
return maxHigh(leftHigh,rightHigh) + 1;
}
bool isBalanced(struct TreeNode* root) {
TreeDeepth(root);
return flag;
}