LeetCode 110 [Balanced Binary Tree]

1509 단어

원제


두 갈래 나무를 정해 고도의 균형을 맞추도록 해라.이 문제에 대해 고도가 균형 잡힌 두 갈래 나무의 정의는 두 갈래 나무의 각 노드의 두 개의 하위 나무의 깊이 차이가 1을 넘지 않는다는 것이다.
두 갈래 나무 A={3,9,20,#,#,15,7},B={3,#,20,15,7}
A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

두 갈래 나무 A는 높이 균형이 잡힌 두 갈래 나무지만 B는 아니다

문제 풀이 사고방식

  • 일반 BST의 문제는 우선 divide & conquer의 사고방식으로 생각한다
  • 두 갈래 나무 한 그루는 균형 두 갈래 나무=>좌자나무는 균형 두 갈래 나무입니까?오른쪽 나무는 균형 잡힌 두 갈래 나무입니까?
  • 만약 임의의 하위 나무가 균형을 이루지 못한다면 전체 나무는 틀림없이 균형을 이루지 못할 것이다
  • 만약에 좌우 나무가 모두 균형이 맞지만 좌우 나무의 차이가 1보다 크면 이 나무는 또 불균형이다
  • 문제는 각각 좌우 트리에 maxDepth를 구하면 균형은 최대 깊이를 되돌리고 불균형은 -1
  • 을 되돌린다.
  • 기교: -1로 균형이 잡힌 두 갈래 나무가 아니라는 것을 나타낸다
  • 전체 코드

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

    좋은 웹페이지 즐겨찾기