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

一、题目描述

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

二、题解

2.1暴力从顶到底

思路：

首先需要 求出树中每个节点的 深度，一个节点的深度 = max(左子树最大深度 ， 右子树最大深度）

有了深度即可判断二叉树 是否平衡，具体做法类似以前序遍历

1. 即对于当前遍历的节点，首先计算左、右子树的深度，如果左右子树的高度差不超过1,

2. 在分别递归遍历左右子节点，至全部节点遍历完毕

class Solution {       public boolean isBalanced(TreeNode root) {           if (root == null) return true;        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);    }    private int depth(TreeNode root) {           if (root == null) return 0;        return Math.max(depth(root.left), depth(root.right)) + 1;    }}

时间复杂度为：

O(n^2) 其中n是二叉树的节点个数

• 最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度为o(n)

• 对于节点p,如果他的深度是d 则求节点p的深度depth(p)最多会被调用d次，因为isBalance()需要所有的节点都满足，每个isBalance都要调用求深度（需要遍历各子树的所有节点）

• 对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d≤h，所以总时间复杂度为O(nlogn)。

• 对于最坏的情况，二叉树形成链式结构，高度为 O(n)O(n)，此时总时间复杂度为 O(n^2)

2.2提前阻断从底向上

本题最优解，不太好想到

思路：

思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

函数recur(root):

1. 递归返回值：

• 当节点root 左 / 右子树的高度差 < 2 ：则返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1 （ - max(left, right) + 1 ）；
• 当节点root 左 / 右子树的高度差 ≥2 ：则返回 −1 ，代表 此子树不是平衡树

2. 递归终止条件：

• 当越过叶子节点时，返回高度 0 ；
• 当左（右）子树高度left== -1时，代表此子树的 左（右）子树 不是平衡树，因此直接返回 −1 ；

函数isBalanced(root) ：

• 返回值： 若 recur(root) != 1 ，则说明此树平衡，返回 truetrue ； 否则返回 falsefalse 。

复杂度分析：

• 时间复杂度 O(N)： N为树的节点数；最差情况下，需要递归遍历树的所有节点。
• 空间复杂度 O(N)： 最差情况下（树退化为链表时），系统递归需要使用 O(N) 的栈空间。

/** * 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) {           return recur(root) != -1;    }    private int recur(TreeNode root){           if(root == null){               return 0;        }        int left = recur(root.left);        if(left == -1){               return -1;        }        int right = recur(root.right);        if(right == -1){               return -1;        }        return Math.abs(left - right) < 2?Math.max(left,right) + 1 : -1;    }       }