LeetCode 101 [Symmetric Tree]

1272 단어

원제


두 갈래 나무를 정해서 그가 자신의 거울인지 검사하라(축 대칭)
예제
    1
   / \
  2   2
 / \ / \
3  4 4  3

대칭 두 갈래 나무예요.
    1
   / \
  2   2
   \   \
   3    3


대칭 두 갈래 나무 아니에요.

문제 풀이 사고방식

  • helper 함수를 써서 답안을 구하지만, helper 함수의 형삼 left와right는 왼쪽 아들과 오른쪽 아들을 가리키는 것이 아니다.그 위의 예를 예로 들면, 우리는 3, 3, 4, 4
  • 를 전입해야 한다
  • Divide and Conquer의 사고방식 - left.left, right.rightleft.right, right.left 모두 대칭이면 전체 트리 대칭
  • 전체 코드

    # 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 isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if root:
                return self.helper(root.left, root.right)
            return True
                
        def helper(self, left, right):
            if left is None and right is None:
                return True
            if left and right and left.val == right.val:
                return self.helper(left.left, right.right) and \
                        self.helper(left.right, right.left)
            return False
    

    좋은 웹페이지 즐겨찾기