给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

 

提示：

  • 树中的节点数在范围 [0, 5000] 内
  • -104 <= Node.val <= 104
Related Topics
  • 树
  • 深度优先搜索
  • 递归
    • \n
  • 👍 681
  • 👎 0
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    //给定一个二叉树，判断它是否是高度平衡的二叉树。 
    //
    // 本题中，一棵高度平衡二叉树定义为： 
    //
    // 
    // 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 
    // 
    //
    // 
    //
    // 示例 1： 
    //
    // 
    //输入：root = [3,9,20,null,null,15,7]
    //输出：true
    // 
    //
    // 示例 2： 
    //
    // 
    //输入：root = [1,2,2,3,3,null,null,4,4]
    //输出：false
    // 
    //
    // 示例 3： 
    //
    // 
    //输入：root = []
    //输出：true
    // 
    //
    // 
    //
    // 提示： 
    //
    // 
    // 树中的节点数在范围 [0, 5000] 内 
    // -104 <= Node.val <= 104 
    // 
    // Related Topics 树 深度优先搜索 递归 
    // 👍 681 👎 0


    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 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 (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;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)