Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
43 lines (38 sloc) 1.07 KB
problem:
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.
----------------------------------------------
solution:
//Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//如果直接对每个结点求depth再比较深度差,会有很多重复计算;
//所以考虑采用后序遍历,每次当求根节点深度时可以查询记录下来的左右子结点的深度来得到
bool isBalanced_aux(TreeNode *root, int *depth)
{
if(root == NULL)
{
*depth = 0;
return true;
}
int left, right;
if(isBalanced_aux(root->left, &left) && isBalanced_aux(root->right, &right))
{
int diff = left - right;
if(diff <= 1 && diff >= -1)
{
*depth = 1 + (left > right ? left : right);
return true;
}
}
return false;
}
bool isBalanced(TreeNode *root)
{
int depth = 0;
isBalanced_aux(root, &depth);
}