aboutsummaryrefslogtreecommitdiff
path: root/balanced_binary_tree.py
blob: a677b56a11bd8df49ff9d998cf9605f75fcb74c3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 110. Balanced Binary Tree
import leetcode

"""
given a binary tree, determine if it is height balanced
"""


class Solution(object):
    def isBalanced(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        self.balanced = True

        def dfs(node):
            if not node:
                return 0
            l, r = dfs(node.left), dfs(node.right)
            if abs(l - r) > 1:
                self.balanced = False
            return max(l, r) + 1

        dfs(root)
        return self.balanced


if __name__ == "__main__":
    obj = Solution()
    r1 = leetcode.treenode_build(vals=[3, 9, 20, None, None, 15, 7])
    r2 = leetcode.treenode_build(vals=[1, 2, 2, 3, 3, None, None, 4, 4])
    print(obj.isBalanced(r1))
    print(obj.isBalanced(r2))