100. Same Tree

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

Same Tree - LeetCode

[문제 설명]

구조랑 순서랑 값이 같으면 같은 트리이므로 true를 반환, 아니면 false 반환.

[처음 생각한 접근 방법]

왼쪽 트리 오른쪽 트리 순서대로 넣어서 두개씩 뽑기.

일단 두 트리를 null이 아닌 애만 넣어준다.

넣어준 후에 스택에 사이즈가 짝수면, q노드 p노드 둘다 요소가 있는 것이므로 구조는 같다.

후에 구조는 같으므로 값만 비교해서 같으면 true 아니면 false 리턴.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();

        if (p == null && q == null) return true;
        if (p != null) queue.offer(p);
        if (q != null) queue.offer(q);
        if (queue.size() % 2 != 0)  return false;

        while (!queue.isEmpty()) {
            TreeNode temp1 = queue.peek();
            TreeNode temp2 = queue.peek();

            if (temp1.val != temp2.val) return false;

            if (temp1.left != null) queue.offer(temp1.left);
            if (temp2.left != null) queue.offer(temp2.left);
            if (queue.size() % 2 != 0) return false;


            if (temp1.right != null) queue.offer(temp1.right);
            if (temp2.right != null) queue.offer(temp2.right);
            if (queue.size() % 2 != 0) return false;
        }

        return true;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();

        if (p == null && q == null) return true;
        if (p != null) stack.push(p);
        if (q != null) stack.push(q);

        // 짝수 개가 아니면 하나는 null
        if (stack.size() % 2 != 0)  return false;

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

            if (temp1.val != temp2.val) return false;

            if (temp1.left != null) stack.push(temp1.left);
            if (temp2.left != null) stack.push(temp2.left);
            if (stack.size() % 2 != 0) return false;

            if (temp1.right != null) stack.push(temp1.right);
            if (temp2.right != null) stack.push(temp2.right);
            if (stack.size() % 2 != 0) return false;
        }

        return true;
    }
}

[리트코드 답안]

public boolean isSameTree(TreeNode p, TreeNode q) {
    if(p == null && q == null) return true;
    if(p == null || q == null) return false;
    if(p.val == q.val)
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    return false;
}

재귀를 이용한 풀이입니다. 보자마자 욕이 나왔는데, 그래도 재귀를 전에 한 번 풀어봐서인지 보자마자 감이 왔습니다.

진짜 재귀는 코드가 간단해서 너무 좋으면서 이해하기 어려워서 힘듭니다.