网上购物网站建设需求,在线购物系统的分析与设计,长春百度关键词搜索,常德建设网站多少钱目录前言题目1.求高度和深度的区别节点的高度节点的深度2. 本题思路分析#xff1a;3. 算法实现4. pop函数的算法复杂度5. 算法坑点前言
在本科毕设结束后#xff0c;我开始刷卡哥的“代码随想录”#xff0c;每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专…
目录前言题目1.求高度和深度的区别节点的高度节点的深度2. 本题思路分析3. 算法实现4. pop函数的算法复杂度5. 算法坑点前言
在本科毕设结束后我开始刷卡哥的“代码随想录”每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。 代码随想录此题链接
题目
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
1.求高度和深度的区别
节点的高度
求节点的高度指的是该节点到叶子节点的最长简单路径的节点数 求节点的高度递归方法时记得使用后序遍历 但是求根节点的高度就是求二叉树的最大深度
节点的深度
求节点的深度指的是根节点到该节点的最长简单路径的节点数 求节点的深度递归方法时记得使用前序遍历
2. 本题思路分析
使用后续遍历因为求的是节点的高度求出节点的左右孩子的高度进行比较如果差值大于1则代表不是平衡二叉树向父节点返回-1告知父节点此树不为平衡二叉树否则返回当前节点的高度当前节点的高度是左右子树的最大值1就是当前节点的高度。
3. 算法实现
代码 //递归法后序遍历因为是求高度所以是后序遍历
//求高度所以使用后序遍历
public boolean isBalanced(TreeNode root) {return getHeightOfTree(root) -1 ? false :true;
}
//递归三部曲
//1.确定返回值和参数 返回值是深度 参数是以当前节点 如果是平衡二叉树则返回树的高度,否则返回-1
//2.确定返回条件
//3.确定单层递归逻辑
public int getHeightOfTree(TreeNode root){if(root null){return 0;}int leftHeight getHeightOfTree(root.left);if(leftHeight -1){//左子树不为平衡二叉树return -1;}int rightHeight getHeightOfTree(root.right);if(rightHeight -1){//右子树不为平衡二叉树return -1;}if(Math.abs(leftHeight - rightHeight) 1){//该节点为根节点的树不为平衡二叉树return 1 Math.max(leftHeight , rightHeight); }else{return -1;}}4. pop函数的算法复杂度
n为总结点数 时间复杂度O(log n × log n) 空间复杂度O(log n)
5. 算法坑点
暂无
