tree 문제 2개 (dfs & bfs) [leetcode]

DFS

가장 깊은 노드 끼리 합산 뒤, 반환하는 문제다.

이 문제의 경우 dfs( Depth First Search )를 통해 풀면 된다. 재귀 함수를 사용하고,

함수의 반환 값은 [ 노드의 값, 노드의 깊이 ] 를 반환 한다.

left 와 right 값을 반환 받았을때 노드의 깊이 를 비교한 뒤,

1. left 노드의 깊이 > right 노드의 깊이 일 경우
   1. left 노드 정보 ( [ 노드의 값, 노드의 깊이] ) 를 반환
2. left 노드의 깊이 == right 노드의 깊이 일 경우
   1. 노드 값 합산 ( left+right노드의 값, left(right) 노드의 깊이] ) 를 반환
3. left 노드의 깊이 < right 노드의 깊이 일 경우
   1. right 노드 정보 ( [ 노드의 값, 노드의 깊이] ) 를 반환

해당 조건을 통해 구현하게 되면 가장 깊은 노드의 합을 반환 할 수 있게 된다.

 

code

# 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
class Solution:
    def dfs(self, node, step):
        if node.left == None and node.right == None:
            return [node.val, step]
        else:
            left_node = None
            if node.left != None:
                left_node = self.dfs(node.left, step+1)
            
            right_node = None
            if node.right != None:
                right_node = self.dfs(node.right, step+1)
            
            if left_node != None and right_node != None:
                if left_node[1] > right_node[1]:
                    return left_node
                elif left_node[1] == right_node[1]:
                    return [left_node[0]+right_node[0], right_node[1]]
                else:
                    return right_node
            elif left_node == None:
                return right_node
            else:
                return left_node
            
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        node_info = self.dfs(root, 0)
        return node_info[0]

 

BFS

트리의 깊이 별로 왼쪽으로 오른쪽으로 노드를 연결 하는 문제다.

( A_node.next = B_node , A_node.depth == B_node.depth)

 

이 경우에는 bfs ( Breadth First Search )를 이용하면 된다.

 

노드를 저장하는 리스트 (이하 node_list)

node_list를 순회하면서 해당 노드들의 자식(left, right) 노드를 저장하는 리스트 (이하 temp_list)

를 만든 뒤,

 

node_list를 순회하면서 자식노드 여부를 검사

존재한다면, 자식 노드를 전부 temp_list에 저장해준다.

 

리스트(temp_list) 를 순회하면서 노드별로 next 값을 리스트의 다음값으로 지정해준다.

(temp_list[0].next = temp_list[1])

node_list를 temp_list로 변경해준다. ( 다음 depth로 넘어간다는 의미)

 

code

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        node_list = []
        node_list.append(root)
        
        while True:
            temp_list = []
            for node in node_list:
                if node != None:
                    if node.left != None:
                        temp_list.append(node.left)
                    if node.right != None:
                        temp_list.append(node.right)
            
            for i in range(len(temp_list)-1):
                temp_list[i].next = temp_list[i+1]
                
            if len(temp_list) == temp_list.count(None):
                break
            
            node_list = temp_list
        return root