- Reference
- ์๊ฐ๋ณต์ก๋: $O(N)$ (Solution ๋ ๋ค)
Solution (Stack)
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
# stack ๋ฐฉ๋ฒ -> ํ์ด์ ๋ฌธ๋ฒ ๋์ ํค๋งด..
# 21ms, 61.63%
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# ๋ฃจํธ๊ฐ ์์ผ๋ฉด ์๋ฌด๊ฒ๋ ์กด์ฌํ์ง ์์ผ๋ ์ฌ์ค์ ๋์นญ์ -> ์ฐธ
if root is None:
return True
# list ํํ์ stack์ left, right ํธ์
stack = [root.left, root.right]
# stack์ด ๋น ๋๊น์ง ๊ณ์ ๋ฐ๋ณต
while stack: # is not None <- ์ด๊ฒ ๋ฌธ์
left_node = stack.pop()
right_node = stack.pop()
# ๋ ๋ค null์ด๋ฉด ์์์ ์ ์ฅํ ํ์ X
if left_node is None and right_node is None:
continue
# null ๊ฐ์ ๋์นญ ํ๋จ
if left_node is None or right_node is None:
return False
# ์๋์ฒ๋ผ ํ ํ์ ์์ด or ๋ฌธ๋ฒ์ด ๊ฒฝ์ฐ ๋ค ์ฒ๋ฆฌํด์ค
# if (left_node.val is None and right_node.val is not None) or (
# left_node.val is not None and right_node.val is None):
# return False
# ๋จ์ ๋ณ์ ๋น๊ต
if left_node.val != right_node.val:
return False
stack.append(left_node.left)
stack.append(right_node.right)
stack.append(left_node.right)
stack.append(right_node.left)
return True
Another Solution (Recursive)
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
# ์ฌ๊ท ๋ฐฉ๋ฒ
# 24ms, 35.79%
def isSymmetric(self, root):
if root is None:
return True
return self.check_node(root.left, root.right)
def check_node(self, left_node, right_node):
if left_node is None and right_node is None:
return True
if left_node is None or right_node is None:
return False
if left_node.val != right_node.val:
return False
return self.check_node(left_node.left, right_node.right) and self.check_node(left_node.right, right_node.left)
Leave a comment