728x90
Top Interview Questions 의 Easy Collection에 있는 문제입니다.
문제는 여기서 볼 수 있습니다.
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- -100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Code:
from typing import Optional
# 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
# stack을 활용한 풀이 : 검토할 양쪽 노드를 append -> 이후 pop하여 검토
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root: return True
stack = [(root.left, root.right)]
while stack:
cur = stack.pop()
l, r = cur[0], cur[1]
if not l and not r: continue
if not l and r or not r and l or l.val != r.val: return False # OR조건 3가지임 유의하기
stack.append((l.right, r.left))
stack.append((l.left, r.right))
return True
# 위의 풀이를 함수화해 간추림 : stack사용 안하고 재귀로 풀이
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def helper(left, right):
if not left and not right: return True
if not left or not right or left.val != right.val: return False
return helper(left.left, right.right) and helper(left.right, right.left)
return helper(root.left, root.right)
설명은 위 코드에 주석으로 적혀 있다.
연결 리스트와 트리 문제가 약한 것 같다. 집중적으로 풀어야겠다...!
728x90
'알고리즘' 카테고리의 다른 글
[Leetcode/Python] Power of Three (0) | 2022.08.27 |
---|---|
[Leetcode/Python] Shuffle an Array (0) | 2022.08.27 |
[Leetcode/Python] Maximum Subarray (0) | 2022.08.25 |
[Leetcode/Python] Palindrome Linked List (0) | 2022.08.23 |
[Leetcode/Python] String to Integer (atoi) (0) | 2022.08.23 |