Description du sujet

Description en anglais

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.

Adresse en anglais

https://leetcode.com/problems/balanced-binary-tree/

Description de la version chinoise

Compte tenu d'un arbre binaire,Pour déterminer si c'est un arbre binaire très équilibré. Dans cette question,Un arbre binaire équilibré en hauteur est défini comme： Un arbre binaire par noeud La différence absolue de hauteur entre les sous - arbres gauche et droit de ne pas dépasser 1 .

Exemple 1： Entrée：root = [3,9,20,null,null,15,7] Produits：true

Exemple 2： Entrée：root = [1,2,2,3,3,null,null,4,4] Produits：false

Exemple 3： Entrée：root = [] Produits：true

Conseils：

• Le nombre de noeuds dans l'arbre est dans la plage [0, 5000] Intérieur

• -104 <= Node.val <= 104

Adresse de la version chinoise

https://leetcode.cn/problems/balanced-binary-tree/

Comment résoudre le problème

Une caractéristique importante de l'arbre de recherche binaire , Les sous - arbres gauche et droit sont également des arbres de recherche binaires

Comment résoudre le problème

Mon édition.

/**
 * 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 {
    public boolean isBalanced(TreeNode root) {
        if (null == root) {
            return true;
        }
        int step = getHeight(root.left) - getHeight(root.right);

        return Math.abs(step) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int getHeight(TreeNode treeNode) {
        if (null == treeNode) {
            return 0;
        }
        return Math.max(getHeight(treeNode.left), getHeight(treeNode.right)) + 1;
    }
}

Version officielle

Méthode 1：Récursion descendante

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

Méthode 2：Récursion du bas vers le haut

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

Résumé

La structure des données est en fait l'utilisation d'une structure spéciale pour augmenter les opérations （Recherche, etc）Efficacité des donnéeso(^▽^)o