Balanced Binary Tree

Question

Problem Statement

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

  1. A)  3            B)    3 
  2.    / \                  \
  3.   9  20                 20
  4.     /  \                / \
  5.    15   7              15  7

The binary tree A is a height-balanced binary tree, but B is not.

题解1 - 递归

根据题意，平衡树的定义是两子树的深度差最大不超过1，显然使用递归进行分析较为方便。既然使用递归，那么接下来就需要分析递归调用的终止条件。和之前的 Maximum Depth of Binary Tree | Algorithm 类似，NULL == root必然是其中一个终止条件，返回0；根据题意还需的另一终止条件应为「左右子树高度差大于1」，但对应此终止条件的返回值是多少？——INT_MAX or INT_MIN？想想都不合适，为何不在传入参数中传入bool指针或者bool引用咧？并以此变量作为最终返回值，此法看似可行，先来看看鄙人最开始想到的这种方法。

C++ Recursion with extra bool variable

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: The root of binary tree.
  17.      * @return: True if this Binary tree is Balanced, or false.
  18.      */
  19.     bool isBalanced(TreeNode *root) {
  20.         if (NULL == root) {
  21.             return true;
  22.         }
  24.         bool result = true;
  25.         maxDepth(root, result);
  27.         return result;
  28.     }
  30. private:
  31.     int maxDepth(TreeNode *root, bool &isBalanced) {
  32.         if (NULL == root) {
  33.             return 0;
  34.         }
  36.         int leftDepth = maxDepth(root->left, isBalanced);
  37.         int rightDepth = maxDepth(root->right, isBalanced);
  38.         if (abs(leftDepth - rightDepth) > 1) {
  39.             isBalanced = false;
  40.             // speed up the recursion process
  41.             return INT_MAX;
  42.         }
  44.         return max(leftDepth, rightDepth) + 1;
  45.     }
  46. };

源码解析

如果在某一次子树高度差大于1时，返回INT_MAX以减少不必要的计算过程，加速整个递归调用的过程。

初看起来上述代码好像还不错的样子，但是在看了九章的实现后，瞬间觉得自己弱爆了… 首先可以确定abs(leftDepth - rightDepth) > 1肯定是需要特殊处理的，如果返回-1呢？咋一看似乎在下一步返回max(leftDepth, rightDepth) + 1时会出错，再进一步想想，我们能否不让max...这一句执行呢？如果返回了-1，其接盘侠必然是leftDepth或者rightDepth中的一个，因此我们只需要在判断子树高度差大于1的同时也判断下左右子树深度是否为-1即可都返回-1，不得不说这种处理方法要精妙的多，赞！

C++

  1. /**
  2.  * forked from http://www.jiuzhang.com/solutions/balanced-binary-tree/
  3.  * Definition of TreeNode:
  4.  * class TreeNode {
  5.  * public:
  6.  *     int val;
  7.  *     TreeNode *left, *right;
  8.  *     TreeNode(int val) {
  9.  *         this->val = val;
  10.  *         this->left = this->right = NULL;
  11.  *     }
  12.  * }
  13.  */
  14. class Solution {
  15. public:
  16.     /**
  17.      * @param root: The root of binary tree.
  18.      * @return: True if this Binary tree is Balanced, or false.
  19.      */
  20.     bool isBalanced(TreeNode *root) {
  21.         return (-1 != maxDepth(root));
  22.     }
  24. private:
  25.     int maxDepth(TreeNode *root) {
  26.         if (NULL == root) {
  27.             return 0;
  28.         }
  30.         int leftDepth = maxDepth(root->left);
  31.         int rightDepth = maxDepth(root->right);
  32.         if (leftDepth == -1 || rightDepth == -1 || \
  33.             abs(leftDepth - rightDepth) > 1) {
  34.             return -1;
  35.         }
  37.         return max(leftDepth, rightDepth) + 1;
  38.     }
  39. };

Java

  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. public class Solution {
  11.     public boolean isBalanced(TreeNode root) {
  12.         return maxDepth(root) != -1;
  13.     }
  15.     private int maxDepth(TreeNode root) {
  16.         if (root == null) return 0;
  18.         int leftDepth = maxDepth(root.left);
  19.         int rightDepth = maxDepth(root.right);
  20.         if (leftDepth == -1 || rightDepth == -1 ||
  21.             Math.abs(leftDepth - rightDepth) > 1) {
  23.             return -1;
  24.         }
  26.         return 1 + Math.max(leftDepth, rightDepth);
  27.     }
  28. }

源码分析

抓住两个核心：子树的高度以及高度之差，返回值应该包含这两种信息。

复杂度分析

遍历所有节点各一次，时间复杂度为 O(n), 使用了部分辅助变量，空间复杂度 O(1).