110. Balanced Binary Tree

public class Solution {
    private int Height(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + Math.Max(Height(root.left), Height(root.right));
    }
    public bool IsBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.Abs(Height(root.left) - Height(root.right)) < 2 &&
               IsBalanced(root.left) && IsBalanced(root.right);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int Height(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + max(Height(root.left), Height(root.right));
    }
    public bool IsBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return abs(Height(root.left) - Height(root.right)) < 2 &&
               IsBalanced(root.left) && IsBalanced(root.right);
    }
}

class Solution {
    private int height(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        return (
            Math.abs(height(root.left) - height(root.right)) < 2 &&
            isBalanced(root.left) &&
            isBalanced(root.right)
        );
    }
}

var height = function (root) {
    if (root == null) {
        return -1;
    }
    return 1 + Math.max(height(root.left), height(root.right));
};

var isBalanced = function (root) {
    if (root == null) {
        return true;
    }
    return (
        Math.abs(height(root.left) - height(root.right)) < 2 &&
        isBalanced(root.left) &&
        isBalanced(root.right)
    );
};

class Solution:
    def height(self, root: TreeNode) -> int:
        if not root:
            return -1
        return 1 + max(self.height(root.left), self.height(root.right))

    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return (
            abs(self.height(root.left) - self.height(root.right)) < 2
            and self.isBalanced(root.left)
            and self.isBalanced(root.right)
        )

func height(root *TreeNode) int {
    if root == nil {
        return -1
    }
    return 1 + max(height(root.Left), height(root.Right))
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return abs(height(root.Left)-height(root.Right)) < 2 &&
        isBalanced(root.Left) &&
        isBalanced(root.Right)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Algorithm

1️⃣

Сначала мы определяем функцию height, которая для любого узла p в дереве T returns:

-1, если p является пустым подtreeм, т.е. null;

1 + max(height(p.left), height(p.right)) в противном случае.

2️⃣

Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. tree T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.

3️⃣

Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:

Если root == NULL, возвращаем true.

Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.

В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).

😎