План курса / Все задачи / Алгоритмы и структуры данных
Сбалансированное дерево
средне
Дан корень бинарного дерева, и нужно вернуть true, если дерево сбалансировано по высоте и false в обратном случае.
Дерево считается сбалансированным по высоте, если высота левого и правого поддерева не отличаются больше чем на 1 для каждой вершины.
ВАЖНО: используй рекурсивную реализацию
Пример 1:
Ввод: root = [1,3,2,4,5,null,null,7,8]
Вывод: false
Объяснение: Для корневой вершины высота левого поддерева - 3, а для правого - 1; 3 - 1 > 1, поэтому дерево не сбалансировано
Пример 2:
Ввод: root = [3,9,20,null,null,15,7]
Вывод: true
Объяснение: Для корневой вершины высота левого поддерева — 1, правого — 2; |2 - 1| <= 1. Для всех остальных вершин разница высот также не превышает 1, поэтому дерево сбалансировано
Ограничения:
Число узлов в дереве >= 1
Высота дерева <= 1000
Значение вершин дерева лежит в диапазоне [-10 000, 10 000] (включительно)
/**
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
// Возвращаем глубину дерева, если оно сбалансировано,
// и -1, если не сбалансировано
private static int BalancedTreeHeight(TreeNode node)
{
if (node == null)
{
return 0;
}
// Находим глубину левого поддерева
// Если глубина = -1, значит поддерево не сбалансировано,
// а значит и всё дерево не сбалансировано
int leftHeight = BalancedTreeHeight(node.left);
if (leftHeight == -1)
{
return -1;
}
// Находим глубину правого поддерева
int rightHeight = BalancedTreeHeight(node.right);
if (rightHeight == -1)
{
return -1;
}
// Если разница глубин > 1, то дерево не сбалансировано
if (Math.Abs(leftHeight - rightHeight) > 1)
{
return -1;
}
// Возвращаем глубину текущего поддерева
return Math.Max(leftHeight, rightHeight) + 1;
}
// Основная функция для проверки сбалансированности дерева
public static bool IsTreeBalanced(TreeNode root)
{
return BalancedTreeHeight(root) != -1;
}
}
#include <algorithm>
using namespace std;
/**
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
// возвращаем глубину дерева если сбалансировано
// и -1 если не сбалансировано
int balancedTreeHeight(TreeNode* node) {
if (node == nullptr) {
return 0;
}
// находим глубину левого поддерева
// если глубина = -1 значит поддерево не сбалансировано,
// а значит и все дерево не сбалансировано
int leftHeight = balancedTreeHeight(node->left);
if (leftHeight == -1) {
return -1;
}
// находим глубину правого поддерева
int rightHeight = balancedTreeHeight(node->right);
if (rightHeight == -1) {
return -1;
}
// если разница глубин > 1, то дерево не сбалансировано
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
return max(leftHeight, rightHeight) + 1;
}
bool isTreeBalanced(TreeNode* root) {
return balancedTreeHeight(root) != -1;
}
package main
// type TreeNode struct {
// Val int
// Left *TreeNode
// Right *TreeNode
// }
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// возвращаем глубину дерева если сбалансировано
// и -1 если не сбалансировано
func balancedTreeHeight(node *TreeNode) int {
if node == nil {
return 0
}
// находим глубину левого поддерева
// если глубина = -1 значит поддерево не сбалансировано,
// а значит и все дерево не сбалансировано
leftHeight := balancedTreeHeight(node.Left)
if leftHeight == -1 {
return -1
}
// находим глубину правого поддерева
rightHeight := balancedTreeHeight(node.Right)
if rightHeight == -1 {
return -1
}
// если разница глубин > 1, то дерево не сбалансировано
if abs(leftHeight - rightHeight) > 1 {
return -1
}
return max(leftHeight, rightHeight) + 1
}
func isTreeBalanced(root *TreeNode) bool {
return balancedTreeHeight(root) != -1
}
import java.util.*;
// class TreeNode {
// int val;
// TreeNode left, right;
// public TreeNode(int value) {
// this.val = value;
// this.left = this.right = null;
// }
// }
class Solution {
// возвращаем глубину дерева если сбалансировано
// и -1 если не сбалансировано
public int balancedTreeHeight(TreeNode node) {
if (node == null) {
return 0;
}
// находим глубину левого поддерева
// если глубина = -1 значит поддерево не сбалансировано,
// а значит и все дерево не сбалансировано
int leftHeight = balancedTreeHeight(node.left);
if (leftHeight == -1) {
return -1;
}
// находим глубину правого поддерева
int rightHeight = balancedTreeHeight(node.right);
if (rightHeight == -1) {
return -1;
}
// если разница глубин > 1, то дерево не сбалансировано
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
public boolean isTreeBalanced(TreeNode root) {
return balancedTreeHeight(root) != -1;
}
}
from typing import *
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
# возвращаем глубину дерева если сбалансировано
# и -1 если не сбалансировано
def balanced_tree_height(node: TreeNode) -> int:
if node is None:
return 0
# находим глубину левого поддерева
# если глубина = -1 значит поддерево не сбалансировано,
# а значит и все дерево не сбалансировано
left_height = balanced_tree_height(node.left)
if left_height == -1:
return -1
# находим глубину правого поддерева
right_height = balanced_tree_height(node.right)
if right_height == -1:
return -1
# если разница глубин > 1, то дерево не сбалансировано
if abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
def is_tree_balanced(root: TreeNode) -> bool:
return balanced_tree_height(root) != -1
/*
class TreeNode {
constructor(value) {
this.val = value;
this.left = null;
this.right = null;
}
}
*/
// возвращаем глубину дерева если сбалансировано
// и -1 если не сбалансировано
export function balancedTreeHeight(node) {
if (node === null) {
return 0;
}
// находим глубину левого поддерева
// если глубина = -1 значит поддерево не сбалансировано,
// а значит и все дерево не сбалансировано
const leftHeight = balancedTreeHeight(node.left);
if (leftHeight === -1) {
return -1;
}
// находим глубину правого поддерева
const rightHeight = balancedTreeHeight(node.right);
if (rightHeight === -1) {
return -1;
}
// если разница глубин > 1, то дерево не сбалансировано
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
export function isTreeBalanced(root) {
return balancedTreeHeight(root) !== -1;
}
