[LeetCode] 100 Same Tree

Description

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

---

풀이

두 개의 트리가 같은지 다른지 확인하는 문제이다.

각 트리의 층별로 비교하려고 BFS를 사용했다.

• 왼쪽과 오른쪽 트리의 값을 꺼내서 둘을 비교한다.

• 왼쪽 노드부터 확인하여 큐에 넣은 뒤 오른쪽 노드를 확인하기 때문에
  -> 왼쪽 노드가 리프노드인 경우 별다른 문장 없이 그냥 넘어가고(오른쪽 노드를 확인해야하기 때문에),
  -> 오른쪽 노드가 리프노드인 경우 continue를 사용하여 넘어가도록 했다.

• 노드가 왼쪽이나 오른쪽 중 하나의 자식만 있을 경우 없는 노드는 큐에 null을 넣어주었다.

• 왼쪽 큐의 크기만큼 돌게 했기 때문에
  -> while이 끝났을 때 오른쪽 큐의 크기가 0보다 크면 false를 반환한다.

---

코드

/**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
        TreeNode leftRoot = p;
        TreeNode rightROot = q;

        Queue<TreeNode> leftQueue = new LinkedList<>();
        Queue<TreeNode> rightQueue = new LinkedList<>();

        leftQueue.offer(p);
        rightQueue.offer(q);

        while (leftQueue.size() > 0) {
            System.out.println("leftQueue.size() > 0");
            TreeNode curLeftNode = leftQueue.poll();
            TreeNode curRightNode = rightQueue.poll();

            if (curLeftNode == null && curRightNode == null) {
                continue;
            } else if (curLeftNode != null && curRightNode != null) {
                if (curLeftNode.val != curRightNode.val) {
                    return false;
                }

                if (curLeftNode.left != null && curLeftNode.right != null) {
                    leftQueue.offer(curLeftNode.left);
                    leftQueue.offer(curLeftNode.right);
                } else if (curLeftNode.left != null) {
                    leftQueue.offer(curLeftNode.left);
                    leftQueue.offer(null);
                } else if (curLeftNode.right != null) {
                    leftQueue.offer(null);
                    leftQueue.offer(curLeftNode.right);
                }

                if (curRightNode.left == null && curRightNode.right == null) {
                    continue;
                } else if (curRightNode.left != null && curRightNode.right != null) {
                    rightQueue.offer(curRightNode.left);
                    rightQueue.offer(curRightNode.right);
                } else if (curRightNode.left != null) {
                    rightQueue.offer(curRightNode.left);
                    rightQueue.offer(null);
                } else {
                    rightQueue.offer(null);
                    rightQueue.offer(curRightNode.right);
                }
            } else {
                return false;
            }
        }

        if (rightQueue.size() > 0) {
            return false;
        }
        return true;
    }
}