Tree_Graph判断是否平衡二叉树@CareerCup_PHP教程
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Tree_Graph判断是否平衡二叉树@CareerCup_PHP教程，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3328字，纯文字阅读大概需要5分钟。
内容图文
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）：
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPsjnyc/NvKOszqrGvbritv6y5sr3o6y1q7K7xr264qGjPC9wPgo8cD7F0LbP0ru/w8r3yse38ca9uuK/ydLUx/PK97XE1+6087jftsi6zdfu0KG437bI1q6y7srHt/G089PaMaGjPC9wPgo8cD7H88r3tcTX7tChuN+2yL/Jss6/vKO6aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZmlnaHRmb3J5b3VyZHJlYW0vYXJ0aWNsZS9kZXRhaWxzLzEyODUxMjMxPC9wPgo8cD48YnI+CjwvcD4KPHA+we3Su9bWveK3qMrHv8nS1NPD1tDQ8rHpwPrH87XDyvfA77XEw7/Su7j20rbX07XEuN+2yKOsyLu687/JtcOhozwvcD4KPHA+ss6/vKO6aHR0cDovL2hhd3N0ZWluLmNvbS9wb3N0cy80LjEuaHRtbDwvcD4KPHA+PGJyPgo8L3A+CjxwPs/Cw+bKx8XQts/Kx7fxxr264rb+subK97XEtPrC66O6PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">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));
}
}
http://www.bkjia.com/PHPjc/735868.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/735868.htmlTechArticleImplement 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...
内容总结
以上是互联网集市为您收集整理的Tree_Graph判断是否平衡二叉树@CareerCup_PHP教程全部内容，希望文章能够帮你解决Tree_Graph判断是否平衡二叉树@CareerCup_PHP教程所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。