logo头像

不忘初心,奋力前行

balanced binary tree

本文于393天之前发表,文中内容可能已经过时,如有问题,请联系我。

题目描述

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.

题目解析

见剑指offer题解(平衡二叉树)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int getDepth(TreeNode *root)
{
if(root == NULL)
return 0;
int leftDepth=getDepth(root -> left);
int rightDepth=getDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
bool isBalanced(TreeNode *root) {
if(root == NULL)
return true;
int leftDepth = getDepth(root -> left);
int rightDepth = getDepth(root -> right);
if(leftDepth > rightDepth + 1 || leftDepth + 1 < rightDepth)
return false;
else
return isBalanced(root->left)&&isBalanced(root->right);
}
支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!