Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
平衡二叉树的定义为:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1, 并且左右两个子树都是一棵平衡二叉树。
思路:
1)先写一个递归的树的高度函数,然后检查子树的高度差是否大于1
2)优化:把检查子树高度差是否大于1的逻辑放在求树的高度的递归函数中,并且遇到非平衡就及时返回。
注:
这道题不同于问一棵树是否平衡(这棵树任意两个叶子结点到根结点的距离之差不大于1):
如上图,为平衡二叉树,但不平衡。
判断一棵树是否平衡可以求树的最大高度和最小高度之差是否大于1。
求树的最小高度可参考:http://blog.csdn.net/fightforyourdream/article/details/12851231
另一种解法是可以用中序遍历求得树里的每一个叶子的高度,然后可得。
参考:http://hawstein.com/posts/4.1.html
下面是判断是否平衡二叉树的代码:
package Tree_Graph;
import CtCILibrary.AssortedMethods;
import CtCILibrary.TreeNode;
public class S4_1 {
// 递归判断树是否平衡二叉树
// Time: O(N^2)
public static boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int heightDiff = getHeight(root.left) - getHeight(root.right);
if(Math.abs(heightDiff) > 1) { // 非平衡
return false;
} else {
return isBalanced(root.left) && isBalanced(root.right);
}
}
// 递归获得树的高度
public static int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
// ========================== Improved version 优化版
// 把判断是否平衡的逻辑放在checkHeight函数里,边计算高度,
// 边判断是否平衡,如果不平衡,直接返回-1
// Time: O(N), Space: O(H), H: height of tree
public static boolean isBalanced2 (TreeNode root) {
if (checkHeight(root) == -1) {
return false;
} else{
return true;
}
}
// 边计算高度边判断是否平衡
public static int checkHeight (TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = checkHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = checkHeight(root.right);
if (rightHeight == -1) {
return -1;
}
int heightDiff = leftHeight - rightHeight;
if (Math.abs(heightDiff) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
public static void main(String[] args) {
// Create balanced tree
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
TreeNode root = TreeNode.createMinimalBST(array);
System.out.println("Root? " + root.data);
System.out.println("Is balanced? " + isBalanced(root));
// Could be balanced, actually, but it's very unlikely...
TreeNode unbalanced = new TreeNode(10);
for (int i = 0; i < 10; i++) {
unbalanced.insertInOrder(AssortedMethods.randomIntInRange(0, 100));
}
System.out.println("Root? " + unbalanced.data);
System.out.println("Is balanced? " + isBalanced(unbalanced));
}
}
分享到:
相关推荐
SIMATIC_S7_GRAPH_V56.exe格式;SIMATIC_S7_GRAPH_V56.exe格式;SIMATIC_S7_GRAPH_V56.exe格式
tensorflow_inception_graph.pb 是 实现deep dream的必须文件
Arduino项目开发 Communication_Graph_Graph.pdf Arduino项目开发 Communication_Graph_Graph.pdf Arduino项目开发 Communication_Graph_Graph.pdf Arduino项目开发 Communication_Graph_Graph.pdf Arduino项目开发 ...
simatic_s7_graph_v53_sp5,simatic_s7_graph_v53_sp5
Object Detection API是谷歌开放的一个内部使用的物体识别系统。2016年10月,该系统在COCO识别挑战中名列第一。它支持当前最佳的实物检测模型,能够在单个图像中定位和识别多个对象。该文件是物体识别API中的ssd_...
name :tensorflow_inception_graph.pb inception v3 .pb file
SIMATIC_S7_GRAPH_V53_SP7
Automat by moor by graph (tree)
Automat mili by graph (tree)
hand_inference_graph of using Neural Networks (SSD) on Tensorflow to do hand detect. https://github.com/molyswu/hand_detection
knowledge_graph_demo-master项目完整代码。。。。。。。。。。。。
hdl_graph_slam hdl_graph_slam是使用3D LIDAR的实时6DOF SLAM的开源ROS软件包。 它基于3D Graph SLAM,并具有基于NDT扫描匹配的测距法估计和环路检测。 它还支持多种图形约束,例如GPS,IMU加速度(重力矢量),IMU...
hand_inference_graph of using Neural Networks (SSD) on Tensorflow to do hand detect. https://github.com/molyswu/hand_detection
Efficient Graph-Based Image Segmentation
基于文章《Fast Approximate Energy Minimization via Graph Cuts》的源代码。Yori Boykov写的关于Graphcut的matlab程序,完整实例。
SIMATIC_S7_GRAPH_V5.3_SP7.7z 支持win7 64位系统
s7_300_GRAPH中文编程手册,s7_300_GRAPH中文编程手册
error signal graph simulation
Graph based image segmentation
资源分类:Python库 所属语言:Python 使用前提:需要解压 资源全名:docker_load_graph-1.0.1-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059