LeetCode - 872. Leaf-Similar Trees

문제 개요

바이너리 트리가 주어졌을 때, 왼쪽부터 오른쪽으로 탐색한 리프 노드를 리프노드 시퀀스라고 한다.

아래와 같이 바이너리 트리가 주어졌을 때, 리프노드 시퀀스는 다음과 같다.

리프 노드 시퀀스 = (6,7,4,9,8)

목표

두개의 바이너리 트리의 리프노드 시퀀스가 같을 경우, true 그렇지 않으면 false를 출력하는 프로그램을 만들어라.

입,출력 예

이해한 부분

바이너리 트리를 search 하는 문제이다. 문제의 의도는 다음과 같이 이해했다.

leaf Node와 일반 노드의 차이를 아는가?

leaf Node: left == null && right ==null

문제에서 어려웠던 부분

트리노드 탐색 방법

BFS(Breadth-first search)

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);

while (!queue.isEmpty()) {
    TreeNode current = queue.poll();

    // target action START
    if (isTarget(current)) {
        action(current);
    }
    // target action END

    // search left -> right with BFS START
    if (exist(current.left)) {
        queue.add(current.left);
    }

    if (exist(current.right)) {
        queue.add(current.right);
    }
    // search left -> right with BFS END
}

DFS(Depth-first search)

Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root)

while (!stack.isEmpty()) {
    TreeNode current = stack.pop();

    // target action START
    if (isTarget(current)) {
        action(current);
    }

    // search left -> right with DFS START
    if (exist(current.right)) {
        queue.add(current.right);
    }

    if (exist(current.left)) {
        queue.add(current.left);
    }
    // search left -> right with DFS END
}

특징	BFS	DFS
target & action	동일	동일
search left -> right	left -> right(FIFO)	right -> left(LIFO)
buffer 자료구조	Queue - add, poll	Stack(Deque) - push, pop

해결 전략

public boolean solution(TreeNode root1, TreeNode root2) {
    return getLeafNode(root1).equals(getLeafNode(root2));
}

회고

TreeNode search 순서가 달라도 상관이 없었다. 그저 LeafNode 값이 제대로 들어와 있는지만 확인한다면 쉽게 풀 수 있다.

처음에 생각했던 TreeNode의 순서의 중요성은 풀고 보니, 무관하였다. boolean 값을 반환하기 때문에 그런 것 같다.

그러나 어떤 순서로 방문하는지는 숙지하자. 좀 더 나은 방법이 있다면 그 방법을 따르자.

추가 serach 방식(BFS, DFS)에 따라 순서가 다르게 저장됨을 깨달았다.

BFS는 각 node의 height-level 순서대로 넣는가 하면, DFS는 leaf Node까지 도달한 후 다시 위로 올라가는 방식에 차이가 있었다.

두 방식의 차이를 인지하자

#graph #coding-interview #leetcode