欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

Tree_Graph 判断是否平衡二叉树 @CareerCup_PHP教程

程序员文章站 2022-05-23 15:29:10
...
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):

Tree_Graph 判断是否平衡二叉树 @CareerCup_PHP教程
喎?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



www.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...