트리(Tree) 예시

바이너리 트리(BinaryTree)

class Node:
  def __init__(self, value=0, left=None, right=None):
    self.value = value
    self.left = left
    self.right = right

class BinaryTree:
  def __init__(self):
    self.root = None

bt = BinaryTree()
bt.root = Node(value=1)
bt.root.left = Node(value=2)
bt.root.right = Node(value=3)
bt.root.left.left = Node(value=4)
bt.root.left.right = Node(value=5)
bt.root.right.right = Node(value=6)

 

BFS(너비우선탐색)

from collections import deque

root = 0

def bfs(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
# BFS 함수 호출
bfs(root)

 

DFS(깊이우선탐색)

1. 호출

def dfs(root):
  if root is None:
    return
  dfs(root.left)
  dfs(root.right)

 

2. 전위 순회

def preorder(cur_node):
  if cur_node is None:
    return
  # 자식 노드중에 자신의 노드 먼저 방문
  print(cur_node.value)
  preorder(cur_node.left)
  preorder(cur_node.right)

 

3. 중위 순회

def inorder(cur_node):
  if cur_node is None:
    return
  
  inorder(cur_node.left)
  # 좌측 자식 노드 방문 후 자신의 노드 방문
  print(cur_node.value)
  inorder(cur_node.right)

 

 

4. 후위 순회

def postorder(cur_node):
  if cur_node is None:
    return
  
  postorder(cur_node.left)  
  postorder(cur_node.right)
  # 자식 노드 방문 후 자신의 노드 방문
  print(cur_node.value)

 

바이너리 트리와 해당 트리에 속한 두개의 노드가 주어졌을 때 두노드의 조상중 가장 낮은 노드 찾기

def LCA(root, p,q):
  if root == None:
    return None
  # 좌측 자식 노드
  left = LCA(root.left, p, q)
  # 우측 자식 노드
  right = LCA(root.right, p, q)
  # 시작노드일 경우
  if root == p or root == q:
    return root
  # 둘 다 값이 있는 경우 공통된 조상
  elif left and right:
    return root
  # 둘 중에 값이 있으면 return
  return left or right

 

주어진 바이너리 트리의 최대 깊이를 반환해라

- 내 풀이(Level-Order)

from collections import deque

def BFS(root, count):
  result = 0
  if root is None:
    return 0
  visited = {}
  q = deque()
  q.append((root, count))
  while q:
    s, cnt = q.popleft()
    visited[s] = 1
    if s.left and s.left not in visited:
      q.append((s.left, cnt + 1))
      result = max(result, cnt + 1)

    if s.right and s.right not in visited:
      q.append((s.right, cnt + 1))
      result = max(result, cnt + 1)
  return result

# 트리 만들기
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)

print(BFS(root, 1))

 

- 강의 풀이(Level-Order)

from collections import deque

def maxDepth(root):
  max_depth = 0
  if root is None:
    return max_depth
  q = deque()
  q.append((root, 1))
  while q:
    cur_node, cur_depth = q.popleft()
    max_depth = max(max_depth, cur_depth)
    if cur_node.left:
      q.append((cur_node.left, cur_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)

print(maxDepth(root))

 

- 내 풀이(Post-Order)

from collections import deque

def DFS(root):
  if root is None:
    return 0
  return max(DFS(root.left),DFS(root.right))+1
  
# 트리 만들기
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)

print(DFS(root))

 

- 강의 풀이(Post-Order)

from collections import deque

def maxDepth(root):
  if root is None:
    return 0
  left_depth = maxDepth(root.left)
  right_depth = maxDepth(root.right)
  return max(left_depth,right_depth)+1
  
# 트리 만들기
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)

print(maxDepth(root))