Balanced 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.

解题方法

不仅要check当前node, 还要check所有的subtree!

可以不断地get两边的substree的max depth, 但是这样需要遍历很多次，我们可以 将maxdepth的过程修改，如果再途中发现有不balanced，就一层一层的往上返回。

Solution

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param A : root node of tree
    # @return an integer
    def isBalanced(self, A):
        if A is None:
            return True
        if self.maxDepth(A) == -1:
            return False
        else:
            return True

    def maxDepth(self, A):
        if A is None:
            return 0

        left = self.maxDepth(A.left)
        right = self.maxDepth(A.right)

        if abs(left-right) > 1 or \
            left == -1 or \
            right == -1:
            return -1

        return 1 + max(left, right)

Reference