[LeetCode] 100. Same Tree

문제

기본 트리 문제이다.

TreeNode 클래스가 주어지며, 2개의 이진트리 p, q가 주어질 때 같은 트리인지 아닌지 확인하는 문제이다.

https://leetcode.com/problems/same-tree/

Same Tree - LeetCode

 

풀이

p와 q의 노드를 저장할 Queue를 생성한다. (pQueue, qQueue)

p와 q를 각각 Queue에 저장한다.

 

pQueue가 비어있을 때까지 다음을 반복한다.

1) pQueue와 qQueue의 노드를 하나씩 꺼낸다.

2) 노드가 둘다 null이면 (1)로 돌아간다.

3) 노드가 둘다 null이 아닌 경우 val이 같은지 확인하고, 꺼낸 노드의 left, right를 모두 각 Queue에 저장한다.

4) 둘 중 하나만 null인 경우 false를 리턴한다.

 

-> 이를 반복한 후 while에서 빠져나오면 같은 트리이므로 true를 리턴한다.

 

코드

public boolean isSameTree(TreeNode p, TreeNode q) {

        Queue<TreeNode> pQueue = new LinkedList<>();
        Queue<TreeNode> qQueue = new LinkedList<>();
        pQueue.add(p);
        qQueue.add(q);

        while (!pQueue.isEmpty()) {
            TreeNode pNode = pQueue.poll();
            TreeNode qNode = qQueue.poll();
            if (pNode == null && qNode == null)
                continue;
            if (pNode != null && qNode != null) {
                if (qNode.val != pNode.val) // value가 다른 경우
                    return false;
                pQueue.add(pNode.left);
                pQueue.add(pNode.right);
                qQueue.add(qNode.left);
                qQueue.add(qNode.right);
            } else { // 둘 중 하나만 null인 경우
                return false;
            }
        }
        return true;
    }