LeetCode之Balanced Binary Tree 平衡二叉树
2023-04-18 14:59:09 时间
判定一棵二叉树是不是二叉平衡树。
链接:https://oj.leetcode.com/problems/balanced-binary-tree/
题目描述:
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.给出一棵二叉树,判断它是不是平衡二叉树。
平衡二叉树被定义每个节点的两个子树高度差不超过1。
这道题目比较简单,
一棵树是不是平衡二叉树,可以输入一个结点,计算它的两棵子树的高度差,然后与1比较,递归进行这个操作就可以完成判定。
回顾一下二叉树的概念,平衡二叉树基于二叉查找树(Binary Search Tree),
二叉查找树或者是一棵空树;
或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
二叉查找树是插入,排序,查找的平均时间复杂度都是O(Log(n)),最差情况是O(n),
二叉树的平衡因子是该结点的左子树的深度减去它的右子树的深度,平衡二叉树的BF因子绝对为1。
下面用Java完成Solution,注意空树的情况:
public class BalancedBinaryTreeSolution {
/**
* 访问局部内部类必须先有外部类对象,此处必须用Static修饰
*/
// public static class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode(int x){ val = x;}
// }
//OJ支持JDK的Math函数
public boolean isBalanced(TreeNode root) {
//注意空树的情况
if(root == null)
return true;
int leftDepth=getDepth(root.left);
int rightDepth=getDepth(root.right);
int altitude=rightDepth-leftDepth;
//注意只有一个顶点的情况
if(Math.abs(altitude)>1)
return false;
else
//递归比较
return isBalanced(root.left) && isBalanced(root.right);
}
private int getDepth(TreeNode node){
if(node == null)
return 0;
//递归求深度
return 1+Math.max(getDepth(node.left), getDepth(node.right));
}
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击