Home >Backend Development >PHP Tutorial >Tree_Graph determines whether to balance a binary tree @CareerCup_PHP tutorial
Tree_Graph determines whether to balance a binary tree @CareerCup_PHP tutorial
- WBOYOriginal
- 2016-07-13 10:37:281299browse
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.
The definition of a balanced binary tree is: it is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, and the left and right subtrees are both balanced binary trees.
Things:
1) First write a recursive tree height function, and then check whether the height difference of the subtrees is greater than 1
2) Optimization: Put the logic of checking whether the subtree height difference is greater than 1 in the recursive function that finds the height of the tree, and return in time when it encounters imbalance.
Note:
This question is different from asking whether a tree is balanced (the difference in the distance between any two leaf nodes of this tree and the root node is not greater than 1):
喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPsjnyc/NvKOszqrGvbritv6y5sr3o6y1q7K7xr264qGjPC9wPgo8cD7F0LbP0ru/w8r3yse38ca9uuK/ydLUx/PK97XE1+6087jftsi6zdfu0K G437bI1q6y7srHt/G089PaMaGjPC9wPgo8cD7H88r3tcTX7tChuN+2yL/Jss6/vKO6aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZmlnaHRmb3J5b3VyZHJlYW0vYXJ0aWNsZS9kZXRhaWxzLz EyODUxMjMxPC9wPgo8cD48YnI+CjwvcD4KPHA+we3Su9bWveK3qMrHv8nS1NPD1tDQ8rHpw PrH87XDyvfA77XEw7/Su7j20rbX07XEuN+2yKOsyLu687/JtcOhozwvcD4KPHA+ss6/vKO6 aHR0cDovL2hhd3N0ZWluLmNvbS9wb3N0cy80LjEuaHRtbDwvcD4KPHA+PGJyPgo8L3A+CjxwPs/Cw+bKx8XQts/Kx7fxxr264rb +subK97XEtPrC66O6PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">package Tree_Graph;
import CtCILibrary.AssortedMethods;
import CtCILibrary.TreeNode;
public class S4_1 {
// Recursively determine whether the tree is balanced binary tree
// 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) { // Unbalanced
return false;
} else {
return isBalanced(root.left) && isBalanced(root.right);
}
}
// Get the height of the tree recursively
public static int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
// ========================== Improved version Optimized version
//Put the logic to determine whether it is balanced in the checkHeight function while calculating the height.
// Judge whether the edge is balanced. If not, return -1 directly.
// 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;
}
}
// Calculate the height while determining whether it is balanced
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