题目:给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1:
110. 平衡二叉树 - 图1
输入:root = [3,9,20,null,null,15,7]
输出:true
示例 2:
110. 平衡二叉树 - 图2
输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

解法1:递归,时间复杂度o(n),空间复杂度o(n)

  1. 先写出求二叉树高度的递归函数-> root=null时返回0,否则返回 1 + 左右递归的最大值

    1. public int getHeight(TreeNode root){
    2. if(root == null)
    3. return 0;
    4. int left = getHeight(root.left);
    5. int right = getHeight(root.right);
    6. return 1 + Math.max(left,right);
    7. }
  2. 在递归左子树和右子树的过程中,一旦出现左右子树高度差绝对值超过1,则返回false;

  3. 依次递归当前函数(左右子树),当左右子树都满足条件时,才返回ture

     public boolean isBalanced(TreeNode root) {
         if(root == null)
             return true;
         if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)
             return false;
         return isBalanced(root.left) && isBalanced(root.right);
    
     }
    
     public int getHeight(TreeNode root){
         if(root == null)
             return 0;
         return 1 + Math.max(getHeight(root.left),getHeight(root.right));
     }