leetcode 100, Same Tree

NJW·2023년 1월 10일

코테

목록 보기

132/170

문제 설명

두 개의 트리가 주어질 때, 두 트리가 같은지를 보는 문제이다.
여기서 중요한 점은 노드의 위치와 노드가 가지는 값이 모두 같아야 한다는 거다.

그렇기에 평소대로 쓰던 dfs나 bfs를 그대로 쓸 수가 없다. 노드의 위치까지 고려를 해줘야 하기 때문이다. 또한 null 값의 처리도 주의해야 한다.
~~문제를 혼자 풀 때는 노드의 위치를 제대로 신경쓰지 못했고 null을 제대로 처리하지 못했다~~

코드 설명

깊이 우선 탐색

변수
만일 두 노드가 null이면 true를 반환한다.
둘 중 하나만 null이면 false를 반환한다.
두 노드가 null이 아니라 값이 있다면 두 값을 비교해서 틀리면 false를 반환한다.
두 노드의 왼쪽 값과 오른쪽 값을 1, 2, 3으로 확인한 후 확인한 두 값이 true일 때만 true를 반환한다.

너비 우선 탐색

변수
0-1. queue, 주어진 두 개의 트리의 노드를 넣는 queue
만일 두 노드가 null이라면 true를 반환한다.
만일 둘 중 하나만 null이라면 false를 반환한다.
둘 다 null이 아니라면 두 개의 노드 값을 queue에 넣어준다.
queue에 값이 존재할 때까지 while문을 돌려준다.
4-1. 큐에서 각각 두 값을 꺼낸다(한 큐에 두 트리의 노드를 넣어주었으니 하나는 첫 번째 트리의 값이고 나머지는 두 번째 트리의 값이다).
4-2. 만일 두 값이 null이라면 continue로 밑의 명령문을 실행하지 않는다. 이 부분이 중요한데, 노드의 값을 비교해야 하기 때문에 노드가 null이면 각 값을 비교할 수 없기 때문이다. 그렇기에 두 노드가 null일 경우는 값을 비교하지 않도록 한다(또한 left와 right 노드가 없기 때문에 해당 노드를 넣는 명령문도 수행을 하지 못하게 막아야 한다).
4-3, 둘 중의 하나만 null이라면 false를 반환한다.
4-4, 둘 다 null이 아니라면 값을 비교해서 다르다면 false를 반환한다.
4-5, 각 노드의 왼쪽 노드와 오른쪽 노드를 넣어준다.

코드

깊이 우선 탐색

class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {

        return bfs(p, q);

    }

    public static boolean bfs(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null){
            return true;
        }
        if(root1 == null || root2 == null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }

        return bfs(root1.left, root2.left) && bfs(root1.right, root2.right);
    }
}