网站备案后怎么做实名认证,在线取公司名字 免费,做个人网站需要哪些,怎么建公司网站教程目录 前序遍历与后续遍历 题目地址#xff1a; 题目#xff1a; 我们直接看题解吧#xff1a; 审题目事例提示#xff1a; 解题方法#xff1a; 难度分析#xff1a; 解题方法分析#xff1a; 解题分析#xff1a; 解题思路#xff1a; 代码实现#xff1a; 补充说明… 目录 前序遍历与后续遍历 题目地址 题目 我们直接看题解吧 审题目事例提示 解题方法 难度分析 解题方法分析 解题分析 解题思路 代码实现 补充说明 代码进一步优化 代码实现自顶向下 前序遍历与后序遍历
下面方法需要用大家不太熟或者想加强一下可以先刷一下 二叉树的前序遍历力扣-CSDN博客 二叉树的后序遍历力扣-CSDN博客 题目地址 110. 平衡二叉树 - 力扣LeetCode 难度简单 乍一看以为有点难其实仔细理解一下发现还行大家可以简单看一下解题思路然后再照着代码看会更容易理解一些。 今天刷平衡二叉树大家有兴趣可以点上面链接看看题目要求试着做一下。
题目
给定一个二叉树判断它是否是高度平衡的二叉树。
注本题高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 我们直接看题解吧 审题目事例提示 平衡二叉树的定义 二叉树的每个节点的左右子树的高度差的绝对值不超过1。 注空树也可以作为平衡二叉树 性质当前树的深度等于左子树深度与右子树的深度中的最大值1 解题方法 根据定义可知一棵若为平衡二叉树当且仅当其所右子树也都是平衡二叉树 因此可以用递归的方法。 方法1、自顶向下递归 方法2、自底向上递归 难度分析 主要考察树及二叉树的相关基础对于初学者来说方法2需要打破思维限制可能难一点。 解题方法分析 方法1我们可能比较容易想得到但是它不是最优的。 简单说一下思路 具体做法类似于二叉树的前序遍历即对于当前遍历到的节点首先计算左右子树的高度如果左右子树的高度差是否不超过 1再分别递归地遍历左右子节点并判断左子树和右子树是否平衡。 这是一个自顶向下的递归的过程。它最大的问题是会产生重复计算对于同一个节点用于计算二叉树高度的函数 height( 会被重复调用导致时间复杂度较高。 但如果使用自底向上的做法则对于每个节点函数 height( 只会被调用一次因此下面着重讲一下方法2. 解题分析 自底向上递归的做法类似于后序遍历对于当前遍历到的节点先递归地判断其左右子树是否平衡再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的则返回其高度高度一定是非负整数否则返回−1。如果存在一棵子树不平衡则整个二叉树一定不平衡。 解题思路 1、在函数isBalanced()中,调用height()参数为树根节点root若最终返回值0则说明此树平衡即返回true反之返回false。 2、创建用于计算二叉树高度的函数height(root) ·判断根节点是否为空空则返回0 ·分别递归调用函数height()获取当前节点左右子树的高度 判断其左右子树高度是否为-1或者左右子树绝对值之差大于1满足则返回-1 若不满足则返回其左右子树最大值1 代码实现
class Solution {public boolean isBalanced(TreeNode root) {return height(root) 0;//若最终返回值不等于-1则说明此树平衡即返回true反之返回 // false。}public int height(TreeNode root) {//创建用于计算二叉树高度的函数height(root)if (root null) {return 0; //判断根节点是否为空空则返回0}int leftHeight height(root.left);//递归调用函数height()获取当前节点左子树的高度int rightHeight height(root.right);//递归调用函数height()获取当前节点右子树的高度if (leftHeight -1 || rightHeight -1 || Math.abs(leftHeight - rightHeight) 1) { //判断其左右子树高度是否为-1或者左右子树绝对值之差大于1return -1; //满足则返回-1} else {//若不满足则返回其左右子树最大值1return Math.max(leftHeight, rightHeight) 1;}}
}
补充说明 第一次调用函数时若根节点为空则整棵树为空树了 代码进一步优化 如果左子树已经返回-1了就不需要再递归右子树了直接返回-1 class Solution {public boolean isBalanced(TreeNode root) {return balanced(root) ! -1;}private int balanced(TreeNode node) {if (node null) return 0;int leftHeight, rightHeight;if ((leftHeight balanced(node.left)) -1//如果左子树已经返回-1了就不需要再递归右子树了直接返回-1|| (rightHeight balanced(node.right)) -1|| Math.abs(leftHeight - rightHeight) 1)return -1;return Math.max(leftHeight, rightHeight) 1;}
}
代码实现自顶向下
class Solution {public boolean isBalanced(TreeNode root) {if (root null) {return true;} else {return Math.abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) isBalanced(root.right);}}public int height(TreeNode root) {if (root null) {return 0;} else {return Math.max(height(root.left), height(root.right)) 1;}}
}
