LeetCode--110--平衡二叉树

问题描述：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

方法1：

通过求子树深度来求子树是否balance。left - right > 1 return False。递归遍历每一个节点。

 class Solution(object):

     def isBalanced(self, root):

         """

         :type root: TreeNode

         :rtype: bool

         """

         if root == None:

             return True

         left = self.getDepth(root.left)

         right = self.getDepth(root.right)

         if abs(left - right) > 1:

             return False

         return self.isBalanced(root.left) and self.isBalanced(root.right)

     def getDepth(self,root):

         if root == None:

             return 0

         left = self.getDepth(root.left)

         right = self.getDepth(root.right)

         return max(left,right) + 1

变体：

 class Solution(object):

     def isBalanced(self, root):

         """

         :type root: TreeNode

         :rtype: bool

         """

         def deep(root):

             if not root:

                 return 0

             l = deep(root.left)

             r = deep(root.right)

             if abs(l-r)>1:

                 self.flag = False

             return max(l,r)+1

         self.flag=True

         deep(root)

         if self.flag == False:

             return False

         else:

             return True

2018-09-09 18:24:35

巴特西

LeetCode--110--平衡二叉树

最新文章

热门文章