C#刷题之#110-平衡二叉树(Balanced Binary Tree)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4074 访问。
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7返回 true 。
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4返回 false 。
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.
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7Return true.
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4Return false.
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4074 访问。
public class Program {
public static void Main(string[] args) {
var root = new TreeNode(1) {
left = new TreeNode(2),
right = new TreeNode(3)
};
var res = IsBalanced(root);
Console.WriteLine(res);
root = new TreeNode(1) {
left = new TreeNode(2) {
left = new TreeNode(3) {
left = new TreeNode(4)
}
},
right = new TreeNode(5) {
right = new TreeNode(6)
}
};
res = IsBalanced2(root);
Console.WriteLine(res);
Console.ReadKey();
}
public static bool IsBalanced(TreeNode root) {
//传统递归法,简单易写
//空树是平衡二叉树,因为左右子树数量都是 0
if(root == null) return true;
//左右子树高度差大于 1,不是平衡二叉树
if(Math.Abs(MaxDepth(root.left) - MaxDepth(root.right)) > 1) return false;
//判定左右子树是否为平衡二叉树
return IsBalanced(root.left) && IsBalanced(root.right);
}
public static int MaxDepth(TreeNode root) {
//计算树每个子树的高度
if(root == null) return 0;
var left = MaxDepth(root.left);
var right = MaxDepth(root.right);
return Math.Max(left, right) + 1;
}
public static bool IsBalanced2(TreeNode root) {
//优化递归法
//此段代码引用自 LeetCode 的提交代码
//由本人添加注释
return MaxDepth2(root) >= 0;
}
public static int MaxDepth2(TreeNode root) {
//如果是空树,判定为平衡的
if(root == null) return 0;
//计算左右子树的高度
var left = MaxDepth2(root.left);
var right = MaxDepth2(root.right);
//如果左子树、右子树或高度差大于 1,则返回 -1
//-1 表示判定为非平衡树,立即返回
//导致调用堆栈在回溯时发现上一次是 -1
//由于代码 left < 0 || right < 0 的存在,会使 -1 逐步上传
//又被回溯到上上一次,一直到无法回溯时为止
//按照原代码作者的部分注释,即不平衡的树会被传染到最上层
//也即当发现一个 -1 时,该代码以非常高的效率判定原树为非平衡的
//因为当前树为平衡的,不能判定原树是不是平衡的
//但当前树为非平衡的,原树肯定是不平衡的
//感谢原作者的代码为我们分享如此巧妙的优化
if(left < 0 || right < 0 || Math.Abs(left - right) > 1) return -1;
return Math.Max(left, right) + 1;
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
}
以上给出2种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4074 访问。
True
False
分析:
显而易见,以上2种算法的时间复杂度均为: 。
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |