problem

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.

分析

此题目要求判断一棵树是否是平衡二叉树，我采用的是类似于 leetcode(543). Diameter of Binary Tree中的解法，根据递归中左右子树的深度，判断是否满足平衡条件，缺点就是由于是递归算法，而不是循环，即使发现不满足条件也要逐层退出，因此此提交只超过了1%（去掉print后超越了50%）。

时间复杂度为 O(n) ， n <script type="math/tex" id="MathJax-Element-33">n</script>为节点个数。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None flag = 0 class Solution(object): def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ global flag flag = 0 def depth(r): if not r: return 0 else: left = depth(r.left) right = depth(r.right) if abs(left - right) > 1: flag = 1 return 1 + max(left, right) depth(root) return True if flag == 0 else False

改进

在discussion中看到一个Java的解法可以不使用全局变量而是利用特殊的返回值进行标记，简化了代码，不过只超过3%的提交(后来发现是忘记去掉print了)。

return -1 作为特殊返回值表明已经达到某种目的，可以省去全局变量，优化递归算法时很有用。

class Solution(object): def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ def depth(r): if not r: return 0 else: left = depth(r.left) right = depth(r.right) if left == -1 or right == -1: return -1 print(left, right) if abs(left - right) > 1: return -1 return 1 + max(left, right) return True if depth(root) != -1 else False

学习别人的代码：

class Solution(object): def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ #优雅，而不是if else return self.height(root) >= 0 def height(self, root): if not root: return 0 left = self.height(root.left) right = self.height(root.right) #把多个return合并到一起 if left < 0 or right < 0 or abs(left - right) > 1: return -1 return max(left, right) + 1