Given a binary tree, check whether it is balanced or not.
Analyze:
Consider a height-balancing scheme where following conditions should be checked to determine if a binary tree is balanced.
An empty tree is height-balanced. A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.
The above height-balancing scheme is used in AVL trees. The diagram below shows two trees, one of them is height-balanced and other is not. The second tree is not height-balanced because height of left subtree is 2 more than height of right subtree.
To check if a tree is height-balanced, get the height of left and right subtrees. Return true if difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.
Code:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
public int height(TreeNode root) {
if (root == null) return 0;
return Math.max(height(root.left), height(root.right)) + 1;
}
}
The complexity of the code above is O(N^2). However, some interviewers may ask to provide solution with O(N) complexity. Below is the solution with O(N) complexity. The main idea is if the subtree is balanced, return the true height, else, return -1. Therefore, the parent node of that unbalanced subtree also has -1 height.
public class Solution {
public boolean isBalanced(TreeNode root) {
return getDepth(root) >= 0;
}
public int getDepth(TreeNode node) {
if (node == null) return 0;
int leftDepth = getDepth(node.left);
if (leftDepth < 0) return -1;
int rightDepth = getDepth(node.right);
if (rightDepth < 0) return -1;
if (Math.abs(leftDepth - rightDepth) > 1) return -1;
return Math.max(leftDepth, rightDepth) + 1;
}
}
Reference:
http://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/
http://blog.theliuy.com/2012/balanced-binary-tree/
Read More:
- Binary tree traversal (preorder, middle order, postorder, hierarchy traversal, depth first, breadth first)
- Get the height of mobile phone status bar through reflection
- Map to vector pair map.second sort
- Several ways to center elements horizontally and vertically
- JS Mobile Page to determine whether it is iPhone X, and then set the corresponding height of the element?
- CSS: several ways to center the box vertically and horizontally
- Square root of X (implementation of binary search)
- Android get screen width and height and get control width and height
- Tensorflow image random_ There seems to be something wrong with the shift function
- Android gets the height and width of the screen
- LeetCode 23. Merge k Sorted Lists(java)
- Leetcode 34 finds the first and last position of an element in the sorted array (medium)
- JavaScript to achieve image rotation effect
- Common causes of Leetcode Runtime Error
- Traversing the background data to generate tree structure
- Howto Install and Configure VTK on Ubuntu
- About java “Error: bad binary operator types”
- How to center the box horizontally and vertically in HTML
- On the dynamic acquisition of expandedheight of sliderappbar in nestedscrollview
- [Two Sigma OA] Longest Chain