그래프 vs 트리 그리고 이진트리

• 트리는 “순환 구조”를 갖지 않는 그래프다. (acyclic)
• 트리는 부모 → 자식 노드를 가리키는 단방향 뿐이다.
• 트리에서 “부모노드는” 하나만 존재한다.
• 트리에서 “루트노드” 는 하나만 존재한다.

이진트리

먼저 트리에서 각 노드가 m개 이하의 자식을 갖고 있으면 m-ary 트리 (다항 트리, 다진 트리) 라고 한다.

여기서 m=2일 때 이진트리라고 구분하여 부른다.

• full binary tre : 모든 노드가 0개 or 2개 의 자식 노드를 갖는다
• complete binary tree : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
• Perfect Binary tree : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 leaf node가 동일한 깊이 or 레벨을 갖는다. 문자 그대로 가장 완벽한 유형의 트리
• 나머지 개념은.. 면접 직전에 보는게 젤 좋다고 생각한다...봐도봐도 까먹음

Maximum Depth of Binary Tree - LeetCode

그저 깊이만을 확인하면 되기 때문에, left child 또는 right child 로 traverse하며 max인 depth를 찾는다. (left, right 둘 다 가봐야 함 - 따라서 재귀적으로 풀어야 한다 )

이 문제에서는 root노드만 존재하는 상황도 depth가 1인 것으로 하고 있다

(:05)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int max = 0; 
    public int maxDepth(TreeNode root) {
        /*
        left or Right child로 traverse 해 나갈 수록 depth가 깊어진다. 
        */
        
        dfs(0,root);
        return max;
        
    }
    public void dfs(int d,TreeNode root){
        if(root == null){
            max = Math.max(d,max);
            return;
        }
        dfs(d+1,root.left);
        dfs(d+1,root.right);
    }

}

더 간단한 풀이는 아래와 같다

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

여러가지 풀이

• 사실 depth만을 구한다 라는 것을 고려한다면 bfs가 더 빨리 떠오르는 경우가 많다.
• BFS로 풀이시, 재귀가 아닌 반복구조로 풀이 할 수가 있다.

파이썬

파이썬에서 큐는 “list”로도 가능하나 “deque” 자료형 사용시, doubly linked list로 구성되어있어, 큐와 스택 연산을 모두 자유롭게 활용가능할 뿐 아니라, 양방향 모두 O(1)에 추출할 수 있다.

• 같은 레벨에 존재하는 노드들의 모든 자식 노드들을 q에 넣는다.
• 이 과정에서 q에는 부모노드(n레벨),자식노드(n+1레벨)가 뒤섞여 있게 되겠지만, q에서 pop 하는 연산 ( 같은 레벨에 있는 노드들을 꺼내는 )은 , 이 연산을 시작할 때의 q의 길이만큼만을 수행하기 때문에, n레벨에 있는 노드들만을 꺼내게 된다.

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        queue = collections.deque([root]) # deque 자료구조
        depth = 0
        while queue:
            depth += 1
            # n 레벨의 모든 노드를 pop 하여 -> 인접노드(자식노드)들을 q에 넣는 과정
            for _ in range(len(queue)):
                cur_root = queue.popleft() # deque에서 popleft는 q상의 front를 추출
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        # BFS 반복 횟수 ==> 깊이
        return depth

• 파이썬에서도 물론 DFS를 사용 가능함. 일단 책에는 나와 달리 BFS로 푸는 예제가 있길래 해당 풀이를 가져와봤다.