题目与示例

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

41.平衡二叉树（2021.11.2） - 图1

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public boolean isBalanced(TreeNode root) {
  18.         return depth(root) != -1;
  20.     }
  22.     public int depth(TreeNode node){
  24.         if(node == null) return 0;
  26.         int leftDepth = depth(node.left);
  27.         if(leftDepth == -1) return -1;
  28.         int rightDepth =depth(node.right);
  29.         if(rightDepth == -1) return -1;
  31.         if(Math.abs(leftDepth-rightDepth)>1){
  32.             return -1;
  33.         }
  34.         return Math.max(leftDepth,rightDepth) +1 ;
  35.     }
  36. }