卖萌的弱渣

I am stupid, I am hungry.

Balanced Binary Tree

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.

Example

Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

1
2
3
4
5
6

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7
The binary tree A is a height-balanced binary tree, but B is not.

Solution

  • Time: O(n)
(Balanced-Binary-Tree.py) download
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
35

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: The root of binary tree.
    @return: True if this Binary tree is Balanced, or false.
    """
    def maxPath(self, root):
        if root.left!=None:
            left = self.maxPath(root.left)
        else:
            left = 0
        if root.right!=None:
            right = self.maxPath(root.right)
        else:
            right = 0

        if left==-1 or right==-1 or abs(left-right)>1:
            return -1
        else:
            return max(left,right)+1

    def isBalanced(self, root):
        # write your code here
        if root == None:
            return True
        if self.maxPath(root) == -1:
            return False
        else:
            return True