剑指 Offer 55 - II. 平衡二叉树
2024-08-28 19:33:49
题目描述
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof
代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
if(abs(leftDepth - rightDepth) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
int getDepth(TreeNode* root) {
if(!root) return 0;
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}
};
思路解析
- 递归实现:若左子树平衡,右子树平衡,且左右子树深度差小于1,则整树平衡。
最新文章
- 代码的坏味道(9)——异曲同工的类(Alternative Classes with Different Interfaces)
- SVN中trunk、branches、tag的使用
- C# 获取计算机信息
- 非root用户 gcc安装
- git 记住密码
- linux 添加用户、权限
- Python中的__init__和__new__介绍
- web前端socket封装库--giraffe
- 166. Fraction to Recurring Decimal -- 将除法的商表示成字符串(循环节用括号表示)
- java NIO经典实例
- shell 编程基础
- 转AOP 介绍
- MOOTOOLS和JQUERY如何同时存在,解决冲突
- java中的四则运算
- JS-将input输入框写入的小写字母全部转换成为大写字母的JS代码
- ACM 畅通工程
- Latex:简介及安装
- 1、jQuery的使用入门
- kernel pwn 入门环境搭建
- redis.exceptions.ConnectionError: Error 111 connecting to localhost:6379. Connection refused.