leetcode算法【110】平衡二叉树

港控/mmm° 2022-11-26 06:58 174阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树，判断它是否是高度平衡的二叉树。
    
    本题中，一棵高度平衡二叉树定义为：
    
    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
    
    示例 1:
    
    给定二叉树 [3,9,20,null,null,15,7]
    
        3
       / \
      9  20
        /  \
       15   7
    返回 true 。
    
    示例 2:
    
    给定二叉树 [1,2,2,3,3,null,null,4,4]
    
           1
          / \
         2   2
        / \
       3   3
      / \
     4   4
    返回 false 。

#### 方案： ####

*  简单题

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isBalanced(TreeNode root) { 
            if(root==null) return true;
            int left =  countChild(root.left);
            if(left==-1) return false;
            int right =  countChild(root.right);
            return right==-1||Math.abs(left-right)>1?false:true;
        }
    
    
        public int countChild(TreeNode root){ 
            if(root==null) return 0;
            else{ 
                int left = countChild(root.left);
                if(left==-1) return -1;//截断遍历，已经发现不平衡了
                int right = countChild(root.right);
                return Math.abs(left-right)>1||right==-1?-1:Math.max(left,right)+1;
            }
        }
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode