Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
Constraints:
-
The number of nodes in the tree is in the range
[0, 5000]. -
-104 <= Node.val <= 104
Solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right)
{
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean isBalanced=true;
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
depth(root);
return isBalanced;
}
private int depth(TreeNode node){
if(node == null){
return 0;
}
int left = depth(node.left);
int right = depth(node.right);
if(Math.abs(left-right) > 1){
isBalanced = false;
}
return Math.max(left,right)+1;
}
}
Here, we are going to solve the problem using similar way of recursion for
traversing the binary tree.
1) Pass root to the depth to find depth of the left tree
and right tree using recursion.
2) If difference of the depth between left and right subtree is greater than
1, then set isBalanced boolean to false. Return
max of left, right subtree to calculate final depth difference.[used during recursion]
3) Finally return isBalanced variable.
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section or contact us through our contact page which will be helpful for us to improve.
Comments
Post a Comment