Algorithm
Problem Nmae: 110. Balanced Binary Tree
problem Link: https://leetcode.com/problems/balanced-binary-tree/
.
Given a binary tree, determine if it is
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int maxDepth(struct TreeNode *root) {
if (root == NULL)
return 0;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
if (l > r)
return l + 1;
else
return r + 1;
}
bool isBalanced(struct TreeNode *root) {
if (root == NULL)
return true;
int l = maxDepth(root->left);
int r = maxDepth(root->right);
int d = l - r;
if (d == 0 || d == 1 || d == -1) {
if (isBalanced(root->left) && isBalanced(root->right)) {
return true;
}
else return false;
}
else return false;
}
void printTreePreOrder(struct TreeNode *p) {
if (p != NULL) {
printf("%d", p->val);
printTreePreOrder(p->left);
printTreePreOrder(p->right);
}
else printf("#");
}
int main() {
struct TreeNode *t = (struct TreeNode *)calloc(7, sizeof(struct TreeNode));
struct TreeNode *p = t;
p->val = 1;
p->left = ++t;
t->val = 2;
p->left->left = ++t;
p->left->right = NULL;
t->val = 3;
p->left->left->left = ++t;
p->left->left->right = NULL;
t->val = 4;
t->left = t->right = NULL;
p->right = ++t;
t->val = 2;
p->right->left = NULL;
p->right->right = ++t;
t->val = 3;
p->right->right->left = NULL;
p->right->right->right = ++t;
t->val = 4;
t->left = t->right = NULL;
printTreePreOrder(p); printf("\n");
printf("%d\n", isBalanced(p)); /* should be false */
printf("%d\n", isBalanced(p->left)); /* should be false */
printf("%d\n", isBalanced(p->left->left)); /* should be true */
printf("%d\n", isBalanced(NULL)); /* should be true */
return 0;
}
Input
root = [3,9,20,null,null,15,7]
Output
true
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isBalanced(TreeNode* root) {
bool res = true;
dfs(root, res);
return res;
}
int dfs(TreeNode* root, bool& res){
if(!root) return 0;
int l = dfs(root->left, res);
int r = dfs(root->right, res);
if(abs(l - r) > 1) res = false;
return max(l, r) + 1;
}
};
Input
root = [3,9,20,null,null,15,7]
Output
true
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
Map < TreeNode, Integer> map = new HashMap<>();
int leftHeight = getHeight(root.left, map);
int rightHeight = getHeight(root.right, map);
if (Math.abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode root, Map < TreeNode, Integer> map) {
if (root == null) {
return 0;
}
if (map.containsKey(root)) {
return map.get(root);
}
int height = 1 + Math.max(getHeight(root.left, map), getHeight(root.right, map));
map.put(root, height);
return height;
}
}
Input
root = [1,2,2,3,3,null,null,4,4]
Output
false
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const isBalanced = function(root) {
return check(root) >= 0 ? true : false
};
const check = (root) => {
if(!root) return 1
const left = check(root.left)
if( left === -1 ) return -1
const right = check(root.right)
if( right === -1 ) return -1
if(Math.abs(left - right) > 1)return -1
return (1 + Math.max(left, right))
}
Input
root = [1,2,2,3,3,null,null,4,4]
Output
false
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.computeHeight(root)!=-1
def computeHeight(self, node):
if not node: return 0
left_h=self.computeHeight(node.left)
right_h=self.computeHeight(node.right)
if left_h==-1 or right_h==-1 or abs(left_h-right_h)>1: return -1
return max(left_h,right_h)+1
Input
root = []
Output
true
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _110_BalancedBinaryTree
{
public bool IsBalanced(TreeNode root)
{
return GetHeight(root) != -1;
}
private int GetHeight(TreeNode current)
{
if (current == null) return 0;
var leftHeight = GetHeight(current.left);
if (leftHeight == -1) return -1;
var rightHeight = GetHeight(current.right);
if (rightHeight == -1) return -1;
if (Math.Abs(leftHeight - rightHeight) > 1) return -1;
return Math.Max(leftHeight, rightHeight) + 1;
}
}
}
Input
root = []
Output
true