剑指offer-39、平衡⼆叉树

题⽬描述

输⼊⼀棵节点数为 n ⼆叉树，判断该⼆叉树是否是平衡⼆叉树。
在这⾥，我们只需要考虑其平衡性，不需要考虑其是不是排序⼆叉树
平衡⼆叉树（ Balanced Binary Tree ），具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过 1 ，并且左右两个⼦树都是⼀棵平衡⼆叉树。
样例解释：

思路及解答

自顶向下递归（基础解法）

平衡树意味着我们需要对⽐任何在同⼀个根下的左右⼦树的⾼度差，还记得之前我们计算树的⾼度么，使⽤递归⽅式来解决，其实这道题与算⾼度差不多，只是两边⾼度需要算出⼀个差值。
算法的主要思想：

• 不断对⽐每两个节点的左右⼦树的最⼤⾼度差，注意取差的绝对值，需要⼩于等于1
  
• 对⽐完左右⼦树之后，需要递归左⼦树以及右⼦树进⾏分别判断，都满⾜才是平衡树
  

1. public class Solution79 {
2.     public boolean IsBalanced_Solution(TreeNode root) {
3.         if (root == null) return true;
4.         // 当前左右⼦树是否平衡以及左右⼦树分别是否平衡
5.         return Math.abs(depth(root.left) - depth(root.right)) <= 1 &&
6.             IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
7.     }
8.     private int depth(TreeNode root) {
9.         if (root == null) {
10.             return 0;
11.         }
12.         // 递归获取深度
13.         return Math.max(depth(root.left), depth(root.right)) + 1;
14.     }
15. }

复制代码

• 时间复杂度 O(n) ：每个节点计算⼀次
  
• 空间复杂度 O(n) ：递归需要使⽤额外堆栈空间
  

笔试面试时，建议首选这个方式，效率最优，代码简洁
封装信息法（面向对象思路）

通过自定义类同时返回高度和平衡信息，代码结构更清晰。

1. public class Solution79 {
2.     public boolean IsBalanced_Solution(TreeNode root) {
3.         // 空树
4.         if (root == null) {
5.             return true;
6.         }
7.         return getHeight(root) != -1;
8.     }
9.     public int getHeight(TreeNode root) {
10.         if (root == null) {
11.             return 0;//空节点高度为0
12.         }
13.         // 左⼦树的⾼度
14.         int left = getHeight(root.left);
15.         if (left < 0) {
16.             return -1;//左子树不平衡，直接返回
17.         }
18.         // 右⼦树的⾼度
19.         int right = getHeight(root.right);
20.         if (right < 0) {
21.             return -1;//右子树不平衡，直接返回
22.         }
23.         
24.         // 检查当前节点是否平衡
25.         return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
26.     }
27. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

喜欢鼓捣这些软件，现在用得少，谢谢分享！

yyds。多谢分享

喜欢鼓捣这些软件，现在用得少，谢谢分享！