트리 순회 - level order traversal

문제

해석

깊이의 정의

문제에서 깊이라는 것은 root 노드에서 얼마나 많이 떨어져 있나를 이야기한다

예제

예제 1

1. root 노드 3
2. 1

⇒ 깊이 : 2

예제 2

1. root 노드 3
2. 5, 1
3. 0, 8

⇒ 깊이 : 3

예제 3

• 노드가 하나도 없을 땐? : 깊이 0
• 노드가 root 노드만 있을 땐? : 깊이 1
• 트리가 한쪽으로만 쭉 나열되어 있을 땐? : 레벨을 확인하면 되는 문제라서 상관없다.

접근

• 트리를 순회해야한다.
• BFS를 사용한다 : 한 레벨에 있는 노드들을 모두 순회 해야한다.

# 큐 선언
q = queue();

# 큐에 뭔가 있다는건 접근할 노드가 있다는 것. 큐에 뭔가 있다면 계속 반복해야함
while q:
	cur_node = q.popleft(); # 큐에 있는 노드(접근 예정 노드)를 방문함
	q.enque(childs) # 해당 큐에 자식들이 있다면 다시 q에 넣는다, 이때 depth도 같이 저장해야한다.

	maxdepth # 지금 depth가 가장 깊은 depth 라는 것을 계속 최신화 해준다

BFS 템플릿

from collections import deque

def levelOrder(root):
    visited = []
    if root is None:
        return 0
    q = deque()
    q.append(root)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

트리노드 구현

현재 리트코드에 보면 list로 root를 주어졌는데 디버깅을 위해서 트리형식으로 다시 만들어본다

class TreeNode:
		def __init__(self, l = None, r = None, v = 0):
			self.left = l
			self.right = r
			self.value = v

root = TreeNode(v = 3)
root.left = TreeNode(v=9)
root.right = TreeNode(v=20)
root.right.left = TreeNode(v=15)
root.right.right = TreeNode(v=7)

maxDepth(root)

구현1 - level order

from collections import deque

def maxDepth(root):
  max_depth = 0
  
  if root is None:
    return 0;
  
  q = deque()
  q.append((root, 1)) # 큐에 저장할때 depth도 같이 저장해야 하기 때문에 튜플 자료구조를 사용해서 저장해준다
  
  while q:
    cur_node, cur_depth = q.popleft() # depth도 같이 저장 되니까 변수 두개에 저장해줘야함
    
    max_depth = max(max_depth, cur_depth) # 최대 깊이 최신화
    
    if cur_node.left:
      q.append((cur_node.left, cur_depth + 1)) # cur_node에 left child를 방문할때는 당연히 level이 한단계 밑으로 갈거니까 depth+1 해줘야함
    
    if cur_node.right:
      q.append((cur_node.right, cur_depth + 1))
    
  return max_depth

class TreeNode:
		def __init__(self, l = None, r = None, v = 0):
			self.left = l
			self.right = r
			self.value = v

root = TreeNode(v = 3)
root.left = TreeNode(v=9)
root.right = TreeNode(v=20)
root.right.left = TreeNode(v=15)
root.right.right = TreeNode(v=7)

maxDepth(root)

구현2 - post order

from collections import deque

def maxDepth(root):
		max_depth = 0
		
		if root is None:
			return max_depth # 만약 child들이 None이면 0을 반환
		
		# left와 right child가 있으면 걔네들이 관리하도록
		left_depth = maxDepth(root.left)
		right_depth = maxDepth(root.right)
  
		# left와 right가 없으면 가장 마지막 노드 (depth = 0)
		# left와 right가 있으면 +1 하면서 root
		# 만약에 같은 레벨에서 더 큰 depth가 있다면 그걸 기준으로 +1 해줘야함
			# --> 왜냐하면 더 큰 depth가 있다는건 그 노드는 child를 가지고 있다는 뜻 
		max_depth = max(left_depth, right_depth) + 1 
		return max_depth

class TreeNode:
		def __init__(self, l = None, r = None, v = 0):
			self.left = l
			self.right = r
			self.value = v

root = TreeNode(v = 3)
root.left = TreeNode(v=9)
root.right = TreeNode(v=20)
root.right.left = TreeNode(v=15)
root.right.right = TreeNode(v=7)

maxDepth(root)