에서 푼 내용을 정리했습니다. 물론 go to dicuss가면 사람들이 솔루션을 다 써놨는데 몇몇 개념이나 방법론 등을 까먹지 않으려고 이 페이지에 정리해두려고 합니다.
preorder, inorder, postorder
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = []
stack = [root]
while stack:
parent = stack.pop()
if parent:
ret.append(parent.val)
stack.append(parent.right)
stack.append(parent.left)
return ret
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = []
stack = []
while True:
if not root:
return []
while True:
stack.append(root)
root = root.left
if not root:
break
while True:
if not stack:
return ret
node = stack.pop()
ret.append(node.val)
if node.right:
root = node.right
break
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res[::-1]
일반적으로 전,중,후위순회를 구현할때 재귀 형식으로 쉽게 했는데 재귀 말고 dfs의 개념으로 기억해도 좋은것같다.(이게 더 활용도 잘되는것같다.) 다만 중위순회는 좀 짜야되고.. 전위순회는 스택 사용해서 오른쪽 자식부터 넣고 왼쪽 자식을 넣는다. 그럼 왼쪽 자식부터 순회할테니 이런식으로 짜면 되고, 후위순회는 전위순회와 반대로 왼쪽 자식부터 넣으면서 루트->오른쪽자식-> 왼쪽자식 순으로 순회한다음 이걸 거꾸로 한게 후위순회이므로 거꾸로 돌려준다.
level order
자식들을 다 돌고나서 그 아래자식들로 내려간다. BFS이므로 큐를 이용해서 짠다.
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res, queue = [], [(root, 0)]
while queue:
curr, level = queue.pop(0)
if curr:
if len(res) < level+1:
res.append([])
res[level].append(curr.val)
queue.append((curr.left, level+1))
queue.append((curr.right, level+1))
return res
maximum depth of tree
dfs던 bfs던 순회하면서 현재 깊이 정보를 저장해놓는다. 현재 깊이가 max 깊이보다 더 깊으면 교체해준다.
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
stack = [[root, 1]]
max_level = 1
if not root:
return 0
while stack:
p, level = stack.pop()
max_level = max(max_level, level)
for child_node in [p.left, p.right]:
if child_node:
stack.append([child_node, level + 1])
return max_level
symmetric tree(거울인지 판별.)
bfs로 돌면서 트리를 그려준다. 그리고 한 단씩 보면서 좌우 대칭이 되는지 확인한다.
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
res, queue = [], [(root, 0)]
if not root:
return True
while queue:
curr, level = queue.pop(0)
if curr:
if len(res) < level+1:
res.append([])
res[level].append(curr.val)
queue.append((curr.left, level+1))
queue.append((curr.right, level+1))
else:
if len(res) < level+1:
res.append([])
res[level].append(None)
for each_layer in res:
if each_layer != each_layer[::-1]:
return False
return True
path sum(자식으로 가는 길의 합)
dfs로 돌면서 자식의 합을 따로 옆에 저장해둔다. leaf일때 질문에서 원하는 답과 같은지 확인한다.
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
stack = [[root, root.val]]
res = []
while stack:
p, t_sum = stack.pop()
is_leaf = not filter(lambda x:x, [p.left, p.right])
for child in [p.left, p.right]:
if child:
stack.append([child, t_sum + child.val])
if is_leaf and t_sum == sum:
return True