平衡⼆叉树 Balanced Binary Tree 具有以下性质它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过 1 并且左右两个⼦树都是⼀棵平衡⼆叉树。样例解释思路及解答自顶向下递归基础解法平衡树意味着我们需要对⽐任何在同⼀个根下的左右⼦树的⾼度差还记得之前我们计算树的⾼度么使⽤递归⽅式来解决其实这道题与算⾼度差不多只是两边⾼度需要算出⼀个差值。算法的主要思想不断对⽐每两个节点的左右⼦树的最⼤⾼度差注意取差的绝对值需要⼩于等于1对⽐完左右⼦树之后需要递归左⼦树以及右⼦树进⾏分别判断都满⾜才是平衡树javapublic class Solution79 { public boolean IsBalanced_Solution(TreeNode root) { if (root null) return true; // 当前左右⼦树是否平衡以及左右⼦树分别是否平衡 return Math.abs(depth(root.left) - depth(root.right)) 1 IsBalanced_Solution(root.left) IsBalanced_Solution(root.right); } private int depth(TreeNode root) { if (root null) { return 0; } // 递归获取深度 return Math.max(depth(root.left), depth(root.right)) 1; } }时间复杂度 O(nlogn) 最差情况下需要遍历树所有节点判断是否平衡需要O(n)。但是判断每个节点最⼤⾼度需要递归左右⼦树需要占⽤ O(log2n) 所以总共占⽤ O(Nlog2n)空间复杂度 O(n) 最差情况下也就是树退化为链表时递归需要使⽤ O(n) 的栈空间严格意义上递归栈也需要空间。自底向上递归优化解法上⾯的计算仔细观察就会发现会有很多重复计算的过程⽐如下⾯的数计算⼦树深度的时候计算 1 的左⼦树和计算 2 的基本都重复了。应该如何避免这种重复计算呢前⾯的是⾃顶向下的⽅式因为每个节点都得把⼦树计算⼀遍才需要重复如果我们从下往上计算那不就避免了重复计算。后序遍历先判断子树平衡性再判断当前节点对⽐逻辑如下如果当前节点为空⾼度为0如果当前节点的左⼦树的⾼度为-1那么说明不平衡否则需要计算右⼦树⾼度同样需要不等于-1如果两者的差不符合⼩于等于1那么说明它们不平衡返回-1。通过这样 -1 异常值就会⼀路返回到最初的调⽤处得到不平衡的结果。javapublic class Solution79 { public boolean IsBalanced_Solution(TreeNode root) { // 空树 if (root null) { return true; } return getHeight(root) ! -1; } public int getHeight(TreeNode root) { if (root null) { return 0;//空节点高度为0 } // 左⼦树的⾼度 int left getHeight(root.left); if (left 0) { return -1;//左子树不平衡直接返回 } // 右⼦树的⾼度 int right getHeight(root.right); if (right 0) { return -1;//右子树不平衡直接返回 } // 检查当前节点是否平衡 return Math.abs(left - right) 1 ? -1 : 1 Math.max(left, right); } }时间复杂度 O(n) 每个节点计算⼀次空间复杂度 O(n) 递归需要使⽤额外堆栈空间笔试面试时建议首选这个方式效率最优代码简洁封装信息法面向对象思路通过自定义类同时返回高度和平衡信息代码结构更清晰。javaclass BalanceInfo { boolean isBalanced; int height; BalanceInfo(boolean isBalanced, int height) { this.isBalanced isBalanced; this.height height; } } public class Solution { public boolean isBalanced(TreeNode root) { return checkBalance(root).isBalanced; } private BalanceInfo checkBalance(TreeNode node) { if (node null) { return new BalanceInfo(true, 0); // 空节点平衡且高度为0 } // 递归检查左右子树 BalanceInfo leftInfo checkBalance(node.left); BalanceInfo rightInfo checkBalance(node.right); // 如果子树不平衡直接返回 if (!leftInfo.isBalanced || !rightInfo.isBalanced) { return new BalanceInfo(false, -1); // 高度值此时不重要 } // 检查当前节点是否平衡 if (Math.abs(leftInfo.height - rightInfo.height) 1) { return new BalanceInfo(false, -1); } // 返回当前节点的平衡信息和高高度 int currentHeight Math.max(leftInfo.height, rightInfo.height) 1; return new BalanceInfo(true, currentHeight); } }