剑指 Offer 55 - II. 平衡二叉树

解题思路：递归

递归的解题步骤：

  1. 将原问题分解成子问题，并确定子问题和原问题之间的递推关系
  2. 确定 base case 的返回值

本题的要求是判断一棵树是否为平衡二叉树。

如果一棵二叉树中任意节点的左右子树的深度相差不超过 1 ，即可将这棵树定义为平衡二叉树。

如果 TreeNode root 为平衡二叉树，那么其左子树和右子树均为平衡二叉树，且两树的高度相差不超过 1

对于如何求一棵树的深度（高度），我们在 剑指 Offer 55 - I. 二叉树的深度 这篇题解中已经给出了方法，所以，这里面我们将获取一棵树的深度 ：getDepth() 直接作为一个可用的函数。

递推关系：

如果 isBalanced(root) 返回 true

  • isBalanced(root.left) 为 true
  • isBalanced(root.right) 为 true
  • abs(getDepth(root.left) - getDepth(root.right)) <= 1 为 true

三者的关系需要使用逻辑与（&&）连接

basecase：

如果 root 为空，直接返回 true

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public boolean isBalanced(TreeNode root) {
  12.         if(root == null){
  13.             return true;
  14.         }
  16.         return isBalanced(root.left) 
  17.             && isBalanced(root.right) 
  18.             && Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1;
  19.     }
  21.     private static int getDepth(TreeNode root) {
  22.         if(root == null){
  23.             return 0;
  24.         }
  25.         return Math.max(getDepth(root.left),getDepth(root.right)) + 1;
  26.     }
  27. }

复杂度分析

  • 时间复杂度：O(N * logN)

时间复杂度最差的情况为满二叉树时，getDepth() 的时间复杂度为 O(N)，满二叉树高度的复杂度为 O(logN)，整体的时间复杂度 = 每层执行的复杂度 × 层数的复杂度 = O(N * logN)

  • 空间复杂度：O(N)

最差情况，当树退化为链表，需要 O(N) 的递归栈调用空间