题目描述（简单难度）

110. Balanced Binary Tree - 图1

判断一棵树是否是平衡二叉树，平衡二叉树定义如下：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

解法一

直接按照定义来吧，并且多定义一个求高度的函数，之前在 104 题 做过。

  1. public boolean isBalanced(TreeNode root) {
  2.     //它是一棵空树
  3.     if (root == null) {
  4.         return true;
  5.     }
  6.     //它的左右两个子树的高度差的绝对值不超过1
  7.     int leftDepth = getTreeDepth(root.left);
  8.     int rightDepth = getTreeDepth(root.right);
  9.     if (Math.abs(leftDepth - rightDepth) > 1) {
  10.         return false;
  11.     }
  12.     //左右两个子树都是一棵平衡二叉树
  13.     return isBalanced(root.left) && isBalanced(root.right);
  15. }
  17. private int getTreeDepth(TreeNode root) {
  18.     if (root == null) {
  19.         return 0;
  20.     }
  21.     int leftDepth = getTreeDepth(root.left);
  22.     int rightDepth = getTreeDepth(root.right);
  23.     return Math.max(leftDepth, rightDepth) + 1;
  24. }

解法二

大家觉不觉得解法一怪怪的，有一种少了些什么的感觉，自己写之前就有这种感觉，写完以后仔细分析了一下。

当我们求左子树的高度时，同样是利用了递归去求它的左子树的高度和右子树的高度。

当代码执行到

  1. isBalanced(root.left) && isBalanced(root.right)

递归的判断左子树和右子树是否是平衡二叉树的时候，我们又会继续求高度，求高度再次进入 getTreeDepth 函数的时候，我们会发现，其实在上一次这些高度都已经求过了。

第二个不好的地方在于， getTreeDepth 递归的求高度的时候，也是求了左子树的高度，右子树的高度，此时完全可以判断当前树是否是平衡二叉树了，而不是再继续求高度。

综上，我们其实只需要求一次高度，并且在求左子树和右子树的高度的同时，判断一下当前是否是平衡二叉树。

考虑到 getTreeDepth 函数返回的是int值，同时高度不可能为负数，那么如果求高度过程中我们发现了当前不是平衡二叉树，就返回-1。

  1. private int getTreeDepth(TreeNode root) {
  2.     if (root == null) {
  3.         return 0;
  4.     }
  5.     int leftDepth = getTreeDepth(root.left); 
  6.     int rightDepth = getTreeDepth(root.right); 
  7.     if (Math.abs(leftDepth - rightDepth) > 1) {
  8.         return -1;
  9.     }
  10.     return Math.max(leftDepth, rightDepth) + 1;
  11. }

上边的代码还是有问题的，

  1. int leftDepth = getTreeDepth(root.left); 
  2. int rightDepth = getTreeDepth(root.right);

如果左右子树都不是平衡二叉树，此时都返回了-1，那么再执行下边的代码。

  1. if (Math.abs(leftDepth - rightDepth) > 1) {
  2.     return -1;
  3. }

它们的差会是 0，不会进入if中，但是本来应该进入 if 返回 -1 的。

所以当发现 leftDepth返回 -1 的时候，我们需要提前返回 -1。rightDepth也会有同样的问题，所以也需要提前返回 -1。

  1. private int getTreeDepth(TreeNode root) {
  2.     if (root == null) {
  3.         return 0;
  4.     }
  5.     int leftDepth = getTreeDepth(root.left);
  6.     if (leftDepth == -1) {
  7.         return -1;
  8.     }
  9.     int rightDepth = getTreeDepth(root.right);
  10.     if (rightDepth == -1) {
  11.         return -1;
  12.     }
  13.     if (Math.abs(leftDepth - rightDepth) > 1) {
  14.         return -1;
  15.     }
  16.     return Math.max(leftDepth, rightDepth) + 1;
  17. }

对于我们要写的 isBalanced函数，修改的话就简单了，只需要调用一次 getTreeDepth函数，然后判断返回值是不是-1就可以了。

  1. public boolean isBalanced(TreeNode root) {
  2.     return getTreeDepth(root) != -1;
  3. }
  5. private int getTreeDepth(TreeNode root) {
  6.     if (root == null) {
  7.         return 0;
  8.     }
  9.     int leftDepth = getTreeDepth(root.left);
  10.     if (leftDepth == -1) {
  11.         return -1;
  12.     }
  13.     int rightDepth = getTreeDepth(root.right);
  14.     if (rightDepth == -1) {
  15.         return -1;
  16.     }
  17.     if (Math.abs(leftDepth - rightDepth) > 1) {
  18.         return -1;
  19.     }
  20.     return Math.max(leftDepth, rightDepth) + 1;
  21. }

总

还是比较简单的，有时候可能一下子想不到最优的思路，所以可以先把常规的想法先写出来以便理清思路，然后尝试着去优化。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情