110. Balanced Binary Tree

题目：

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.

Hide Tags

Tree Depth-first Search

链接： http://leetcode.com/problems/balanced-binary-tree/

一刷，recursive解法，时间复杂度：O(N²)

 1 class Solution(object):
 2     def calculate_depth(self, root):
 3         if not root:
 4             return 0
 5         return max(self.calculate_depth(root.left), self.calculate_depth(root.right)) + 1
 6 
 7     def isBalanced(self, root):
 8         if not root:
 9             return True
10         return self.isBalanced(root.left) and self.isBalanced(root.right) and 
11         abs(self.calculate_depth(root.left) - self.calculate_depth(root.right)) <= 1

上面的解法中，求左右子树是否balance和求他们的深度是完全重复的。所以每当向上计算到一个节点时，还需要向下找depth，我们可以把两个方面合并成一个，最终只向一个方向（向上）走

 1 class Solution(object):
 2     def isBalanced(self, root):
 3         return self.calculate_depth(root) != -1
 4 
 5     @staticmethod
 6     def calculate_depth(root):
 7         if not root:
 8             return 0
 9         left_depth = Solution.calculate_depth(root.left)
10         if left_depth == -1:
11             return -1
12         right_depth = Solution.calculate_depth(root.right)
13         if right_depth == -1:
14             return -1
15         if abs(left_depth - right_depth) <= 1:
16             return max(left_depth, right_depth) + 1
17         else:
18             return -1

2/17/2017, Java, 薅羊毛

这道题一开始完全算错了，以下例子通不过：1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5

此例按照本题要求应该是true，但是开始理解成从root下去的差不能超过1。做起来又麻烦又错。

 1 public class Solution {
 2     public boolean isBalanced(TreeNode root) {
 3         if (subtreeDepth(root) == -1) return false;
 4         return true;
 5     }
 6     int subtreeDepth(TreeNode root) {
 7         if (root == null) return 0;
 8         int depthL = subtreeDepth(root.left);
 9         if (depthL == -1) return -1;
10         int depthR = subtreeDepth(root.right);
11         if (depthR == - 1) return -1;
12         
13         if (depthL - depthR > 1 || depthR - depthL > 1) return -1;
14         return Math.max(depthL, depthR) + 1;
15         
16     }
17 }

5/8/2017

算法班

时间复杂度不好O(n^2)top down，应该参考2/7/2017的解法O(n) bottom up

 1 public class Solution {
 2     /**
 3      * @param root: The root of binary tree.
 4      * @return: True if this Binary tree is Balanced, or false.
 5      */
 6     public boolean isBalanced(TreeNode root) {
 7         if (root == null) return true;
 8         if (isBalanced(root.left) && isBalanced(root.right) && Math.abs(subtreeHeight(root.left) - subtreeHeight(root.right)) <= 1) return true;
 9         return false;
10     }
11     private int subtreeHeight(TreeNode root) {
12         if (root == null) return 0;
13         return Math.max(subtreeHeight(root.left), subtreeHeight(root.right)) + 1;
14     }
15 }

别人的

https://discuss.leetcode.com/topic/7798/the-bottom-up-o-n-solution-would-be-better

关于blanced tree的一些讨论，有AVL和红黑树

https://discuss.leetcode.com/topic/276/two-different-definitions-of-balanced-binary-tree-result-in-two-different-judgments