LeetCode 110. 平衡二叉树（二叉树高度）
LeetCode 110. 平衡二叉树（二叉树高度）
Michael阿明
发布于 2021-02-19 22:11:17
发布于 2021-02-19 22:11:17
1. 题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
限制：
1 <= 树的结点个数 <= 10000《剑指Offer》同题：面试题55 - II. 平衡二叉树
2. 解题
- 递归求二叉树左右子树高度
- 当中任何一个的子树高度差超过1，停止搜索
在这里插入图片描述
class Solution {
public:
bool isBalanced(TreeNode* root) {
bool bal = true;
balence(root,bal);
return bal;
}
int balence(TreeNode* root, bool &bal)
{
if(!bal)
return -1;
if(root == NULL)
return 0;
int left_height = balence(root->left,bal);
int right_height = balence(root->right,bal);
if(abs(left_height-right_height)>1)
bal = false;
return max(left_height,right_height)+1;
}
};
在这里插入图片描述
class Solution {
bool balanced = true;
public:
bool isBalanced(TreeNode* root) {
depth(root);
return balanced;
}
int depth(TreeNode* root)
{
if(!balanced || !root)
return 0;
int depthL = depth(root->left);
int depthR = depth(root->right);
if(abs(depthL - depthR) > 1)
balanced = false;
return 1+max(depthL, depthR);
}
};本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录