파이문

101. Symmetric Tree 본문

문제 풀이/leetcode

101. Symmetric Tree

민Z 2017. 3. 26. 23:09
728x90

101. Symmetric Tree

(https://leetcode.com/problems/symmetric-tree/#/description)



대칭이 되는 트리인지 아닌지를 판별하는 문제입니다.

아래와 같이 가운데(?) 를 기준으로 접혀진다면(대칭이 된다면) True를 리턴하고


    1
   / \
  2   2
 / \ / \
3  4 4  3

한쪽이 비거나, 다른 숫자가 들어가거나 등등 대칭이 되지 않는다면 False를 리턴합니다.


    1
   / \
  2   2
   \   \
   3    3


Easy 문제이기 때문에 어렵게 생각할 필요가 없습니다.

문제 그대로 맨 왼쪽은 맨 오른쪽과 같아야 하고, 가장 왼쪽의 오른쪽은 (형제 노드는) 가장 오른쪽의 왼쪽 노드 (형제 노드)와 같으면 됩니다. 


재귀로 계속 체크해나가면서, None이면 가장 끝의 노드이니 그 때 두 값이 동일한지에 대해 리턴하거나(대칭이라면 똑같은 depth에서 None이겠죠), 둘이 같지 않다면 False를 리턴하면 됩니다.

# 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 is None:
            return True
        
        return self.check(root.left, root.right)
    
    def check(self, left_node, right_node):
        if left_node is None or right_node is None:
            return left_node == right_node
            
        if left_node.val != right_node.val:
            return False
        
        return self.check(left_node.left, right_node.right) and self.check(left_node.right, right_node.left)


'문제 풀이 > leetcode' 카테고리의 다른 글

3. Longest Substring Without Repeating Characters  (0) 2019.07.08
2. Add Two Numbers  (0) 2019.06.16
518. Coin Change 2  (0) 2017.04.09
540. Single Element in a Sorted Array  (0) 2017.03.26
Number of Boomerangs  (0) 2017.01.08
Comments