怎么建设外贸网站,余姚网,自己做网站怎么能被访问,家里的网络用哪个公司描述
输入一棵节点数为 n 二叉树#xff0c;判断该二叉树是否是平衡二叉树。
在这里#xff0c;我们只需要考虑其平衡性#xff0c;不需要考虑其是不是排序二叉树
平衡二叉树#xff08;Balanced Binary Tree#xff09;#xff0c;具有以下性质#xff1a;它是一棵空…描述
输入一棵节点数为 n 二叉树判断该二叉树是否是平衡二叉树。
在这里我们只需要考虑其平衡性不需要考虑其是不是排序二叉树
平衡二叉树Balanced Binary Tree具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
样例解释 样例二叉树如图为一颗平衡二叉树
注我们约定空树是平衡二叉树。 数据范围n≤100n≤100,树上节点的val值满足 0≤n≤10000≤n≤1000
要求空间复杂度O(1)O(1)时间复杂度 O(n)O(n)
输入描述
输入一棵二叉树的根节点
返回值描述
输出一个布尔类型的值
示例1
输入
{1,2,3,4,5,6,7}
返回值
true
示例2
输入
{}
返回值
true递归实现
public class Solution {public int deep(TreeNode root){if(rootnull){return 0;}int leftdeep(root.left);int rightdeep(root.right);if(leftright){return left1;}else{return right1;}}public boolean IsBalanced_Solution(TreeNode root) {if(rootnull){return true;}int leftdeep(root.left);int rightdeep(root.right);if(left-right1||right-left1){return false;}return IsBalanced_Solution(root.left)IsBalanced_Solution(root.right);}
}
思路
一个求左右子树深度的方法deepdeep方法可递归调用deep方法再次调用的参数为传入节点的左右子树最后返回左右节点的值。结束标志是左右子树为空返回0
从根节点开始调用deep方法判断左右子树深度之差。递归调用该方法参数为左右子树节点。结束标志是左右子树为0 自底向上 实现代码
public class Solution {public boolean IsBalanced_Solution(TreeNode root) {//空树也是平衡二叉树if(root null)return true;return getdepth(root) ! -1;}public int getdepth(TreeNode root) {if(root null)return 0;//递归计算当前root左右子树的深度差int left getdepth(root.left);//当前节点左子树不平衡则该树不平衡if(left 0) return -1;int right getdepth(root.right);//当前节点右子树不平衡则该树不平衡if(right 0) return -1;//计算深度差return Math.abs(left - right) 1 ? -1 : 1 Math.max(left, right);}
}时间复杂度ON
空间复杂度ON 附录Math函数的方法Math的几个方法Math.round()、Math.ceil()、Math.floor()和Math.abs()记录一下_MingFlying的博客-CSDN博客
