Leetcode解题-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.

分析

检查二叉树是否平衡，递归法很简单。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def isBalancedR(self, root):
        if not root:
            return (True, 0)
        f1, h1 = self.isBalancedR(root.left)
        f2, h2 = self.isBalancedR(root.right)
        f = f1 and f2 and abs(h1 - h2) < 2
        return f, max(h1, h2) + 1

    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        f, h = self.isBalancedR(root)
        return f

热评文章