[LeetCode] Balance Binary Tree python 파이썬 (recursion)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):        
        if root == None:
            return 0        
        else:
            return max( self.maxDepth(root.left), self.maxDepth(root.right)) + 1                               
        
    
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None:
            return True
        
        else:
            if abs( self.maxDepth(root.left) - self.maxDepth(root.right) ) > 1:
                return False
            else:
                return self.isBalanced(root.left) and self.isBalanced(root.right) 

maxDepth라는 함수는 Maximum Depth of Binary Tree 여기에 있는 문제를 활용해서 left와 right의 maximum depth를 구한뒤 차이가 1보다 크면(not balanced) False

 

아무래도 시간이 더 소요 (64ms)

 

출처: pythonfiddle.com/leetcode110-balanced-binary-tree/

---

좀 더 빠른 솔루션

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    # @param root, a tree node
    # @return a boolean
    def isBalanced(self, root):
        def getHeight(root):
            if root is None:
                return 0
            
            left_height, right_height = getHeight(root.left), getHeight(root.right)
            
            if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
                return -1
            
            return max(left_height, right_height) + 1
        return (getHeight(root) >= 0)

 

left_height < 0 라는 것의 의미?

abs(left_height - right_height) > 1 일 경우에만 발생.

좀 더 생각해봐야 할듯