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

题目：平衡二叉树

题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 解决方案： 从顶至底（暴力法） 构造一个获取当前节点最大深度的方法 getHight() ，通过比较左右子树最大高度差Math.abs(left-right)，来判断以此节点为根节点下是否是二叉平衡树； 从顶至底DFS，以每个节点为根节点，递归判断是否是平衡二叉树： 若所有根节点都满足平衡二叉树性质，则返回 True ； 若其中任何一个节点作为根节点时，不满足平衡二叉树性质，则返回False。 本方法产生大量重复的节点访问和计算，最差情况下时间复杂度 O(N^2)。 代码实现：

import java.util.*;public class Solution {    public boolean IsBalanced_Solution(TreeNode root) {        if(root==null) {			return true;		}		//当节点不为空时，找到root左节点的高度		int left=getHight(root.left);		//找到root右节点的高度		int right=getHight(root.right);		//左节点和右节点的高度之和小于等于1 && root的左子树/右子树同样满足这个条件        if((Math.abs(left-right)>1)){            return false;        }else{            //每一层都有相同的特性           return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);        }    }	private int getHight(TreeNode root) {		if(root==null) {			return 0;		}		int left=getHight(root.left);		int right=getHight(root.right);		return Math.max(left, right)+1;	}}

ps: 来源于力扣评论区某位大佬的想法

从底至顶（提前阻断法） 对二叉树做深度优先遍历DFS，递归过程中： 终止条件：当DFS越过叶子节点时，返回高度0； 返回值： 从底至顶，返回以每个节点root为根节点的子树最大高度(左右子树中最大的高度值加1max(left,right) + 1)； 当我们发现有一例 左/右子树高度差 ＞ 1 的情况时，代表此树不是平衡树，返回-1； 当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回-1，避免后续多余计算。 最差情况是对树做一遍完整DFS，时间复杂度为 O(N)。 代码实现：

public class Solution {    public boolean IsBalanced_Solution(TreeNode root) {        if(root==null) {			return true;		}		return getHight(root)!=-1;    }	private int getHight(TreeNode root) {		if(root==null) {			return 0;		}		int left=getHight(root.left);		if(left==-1) {return -1;}		int right=getHight(root.right);		if(right==-1) {return -1;}		return Math.abs(left-right)<2?Math.max(left, right)+1:-1;	}}