Leetcode NO.110 Balanced Binary Tree 平衡二叉树
2021/12/26 23:37:39
本文主要是介绍Leetcode NO.110 Balanced Binary Tree 平衡二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 1.问题描述
- 2.测试用例
- 示例 1
- 示例2
- 示例3
- 3.提示
- 4.代码
- 1.自顶向下
- code
- 复杂度
- 2.自底向上
- code
- 复杂度
- 1.自顶向下
1.问题描述
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
2.测试用例
示例 1
输入:root = [3,9,20,null,null,15,7] 输出:true
示例2
输入:root = [1,2,2,3,3,null,null,4,4] 输出:false
示例3
输入:root = [] 输出:true
3.提示
- 树中的节点数在范围
[0, 5000]
内 -104 <= Node.val <= 104
4.代码
1.自顶向下
code
/** * 自顶向下 * @param root 根节点 * @return 是否是高度平衡的二叉树 */ public boolean isBalancedWithPre(TreeNode root) { if (root == null) { return true; } return Math.abs(getTreeHeight(root.left) - getTreeHeight(root.right)) <= 1 && isBalancedWithPre(root.left) && isBalancedWithPre(root.right); } /** * 获取树的高度 * @param node 节点 * @return 树高度 */ public int getTreeHeight(TreeNode node) { if (node == null) { return 0; } return Math.max(getTreeHeight(node.left), getTreeHeight(node.right)) + 1; }
复杂度
* 时间复杂度:O(nlogn) * 空间复杂度:O(logn)
2.自底向上
code
/** * 自底向上 * 时间复杂度O(n) * 空间复杂度O (logn) * * @param root 根节点 * @return 是否是高度平衡的二叉树 */ public boolean isBalancedWithPost(TreeNode root) { return balanceHeight(root) > -1; } /** * 获取树有效高度 * @param node 节点 * @return 树高度 */ public int balanceHeight(TreeNode node) { if (node == null) { return 0; } int left = balanceHeight(node.left); int right = balanceHeight(node.right); if (left == -1 || right == -1 || Math.abs(left - right) > 1) { return -1; } return Math.max(left, right) + 1; }
复杂度
* 时间复杂度O(n) * 空间复杂度O (logn)
这篇关于Leetcode NO.110 Balanced Binary Tree 平衡二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享