二叉树：判断一个树是否是平衡二叉树

判断一个树是否是平衡二叉树

题目：给定一个二叉树，判断其是否是平衡二叉树。

方法一：

bool isBalancedTree(TreeNode* root)
{if(root == NULL)    return true;int Lh = getHeight(root->left);int Rh = getHeight(root->right);int h = Lh - Rh;if(h < -1 || h > 1){return false;}bool Ltree = isBalancedTree(root->left);bool Rtree = isBalancedTree(root->right);if(!Ltree || !Rtree){return false;}return true;
}int getHeight(TreeNode *root)
{if(root == NULL){return 0;}int Hleft = getHeight(root->left);int Hright = getHeight(root->right);return max(Hleft,Hright) + 1;
}

方法二:本方法是对方法一的代码优化，原理一样。

int level(TreeNode *root)
{if(root == NULL)    return 0;return 1 + max(level(root->left),level(root->right));
}int isBalanced(TreeNode *root)
{if(root == NULL)    return true;int factor = abs(level(root->left) - level(root->right));return factor < 2 && isBalanced(root->left) && isBalanced(root->right);
}

方法三：isBalanced返回当前节点的高度，用-1表示树不平衡，将计算结果自底向上地传递，并且确保每个节点只被计算一次，复杂度为O(n)。

//返回当前节点的高度，-1代表不平衡.
int isBalancedHelper(TreeNode* root)
{if(root == NULL) return 0;int Lh = isBalancedHelper(root->left);int Rh = isBalancedHelper(root->right);if(Lh == -1 || Rh == -1){return -1;}if(abs(Lh - Rh) > 1){return -1;}return max(Lh,Rh) + 1;
}bool isBalancedTree(TreeNode *root)
{return (isBalancedHelper(root) != -1);
}