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

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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)