给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
您在真实的面试中是否遇到过这个题？
image.png
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
/*
这个思路是 写了一个getdeep的函数，函数的返回值是树的深度
然后isbal函数 前序遍历每一个节点，然后调用getdeep的函数，判断自己左右子树的高度，判断这个节点是不是平衡的。
这个isbal 函数的判断过程 使用一个 引用，即void isbal(TreeNode * root,int & flag)；
如果不平衡，就让它等于=1，而没有采取返回值的策略。因为实在想不到什么好的设计思路，可以很好的思路处理返回值。
这里挖一个坑，以后有了好的想法，再来补。
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
int getdeep(TreeNode *p){
if(p==NULL){
return 0;
}
int deep_left=0;
int deep_right=0;
if(p->left!=NULL){
deep_left=getdeep(p->left);
}
if(p->right!=NULL){
deep_right=getdeep(p->right);
}
return deep_left>deep_right?deep_left+1:deep_right+1;
}
void isbal(TreeNode * root,int & flag){
if(root!=NULL){
isbal(root->left,flag);
//判断当前节点
int dl=getdeep(root->left);
int dr=getdeep(root->right);
if((dl-dr>1)||(dl-dr)<-1)
{
flag=0;
}
isbal(root->right,flag);
}
}
bool isBalanced(TreeNode *root) {
// write your code here
int flag=1;
isbal(root,flag);
return flag;
}
};
