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

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.

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

21

查看详情

平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1， 并且左右两个子树都是一棵平衡二叉树。

思路：

1）先写一个递归的树的高度函数，然后检查子树的高度差是否大于1

2）优化：把检查子树高度差是否大于1的逻辑放在求树的高度的递归函数中，并且遇到非平衡就及时返回。

注：

立即学习“PHP免费学习笔记（深入）”；

这道题不同于问一棵树是否平衡（这棵树任意两个叶子结点到根结点的距离之差不大于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