本文共 1432 字，大约阅读时间需要 4 分钟。

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3

/

9 20 / 15 7 返回 true 。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java

常规思路，效率不高

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */ //递归class Solution {
       public int depth(TreeNode root){
           if(root==null) return 0;        return Math.max(depth(root.left),depth(root.right))+1;    }    public boolean isBalanced(TreeNode root) {
           if(root==null)  return true;        return isBalanced(root.left) && isBalanced(root.right) && (Math.abs(depth(root.left)-depth(root.right))<=1);    }}

优化，每个节点只遍历一次

后续遍历，一边遍历一边其记录深度，一边遍历一边判断是否平衡

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {
       public int isBalance(TreeNode root){
           if(root==null) {
               return 0;        }         int left=isBalance(root.left);        int right=isBalance(root.right);        if(left==-1|| right==-1) return -1;        return Math.abs(left-right)>1? -1: Math.max(left,right)+1;            }    public boolean isBalanced(TreeNode root) {
         return isBalance(root)==-1? false:true;    }}