平衡二叉树

---

题目：

题解：

1、先序遍历 + 判断深度 （从顶至底）

• 解题思路：思路是构造一个获取当前子树的深度的函数 depth(root) （即 [二叉树的深度 ][https://nuc462.github.io/2022/06/04/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6/]），通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

• 复杂度分析：

  

• 代码：

  // 先序遍历 + 判断深度 （从顶至底）
  class Solution {
      public boolean isBalanced(TreeNode root) {
          if(root == null) return true;
          return Math.abs(maxDepth(root.left) - maxDepth(root.right) ) <= 1 && isBalanced(root.left) && isBalanced(root.right);
      }
      int maxDepth(TreeNode root) {
          if(root == null) return 0;
          return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
      }
  }

2、后序遍历 + 剪枝 （从底至顶）

• 解题思路：对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

• 复杂度分析：

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

• 代码：

  // 后序遍历 + 剪枝 （从底至顶）
  class Solution2 {
      public boolean isBalanced(TreeNode root) {
          return recur(root) != -1;
      }
      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;
      }
  }