[LeetCode] 100. Same Tree #Easy #Java

문제
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.

예제 1

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

예제 2

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

예제 3

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

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

 

문제풀이

import java.util.Stack;

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1. 변수 선언 및 초기화
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        // 2. 중위 순회
        while ((p != null || !stackP.isEmpty()) && (q != null || !stackQ.isEmpty())) {
            // 왼쪽 자식 노드로 이동
            while (p != null && q != null) {
                stackP.push(p);
                stackQ.push(q);

                p = p.left;
                q = q.left;
            }

            // 유효성 체크
            if (p == null ^ q == null) return false;

            // 부모 노드로 이동
            p = stackP.pop();
            q = stackQ.pop();

            // 유효성 체크
            if (p.val != q.val) return false;

            // 오른쪽 자식 노드로 이동
            p = p.right;
            q = q.right;
        }

        // 3. 반환
        return p == null && q == null;
    }
}

• 원래는 다음 코드와 같이 조건을 작성했었는데, 맘이 안 들어서 고민하다가 XOR 연산을 코드에 처음 써봤다.

 

if ((p != null && q != null) && (p == null || q == null)) return false;

그동안 조건문을 작성할 때 AND 아니면 OR만 고려했는데, 앞으로는 판단할 때 XOR도 사용 할 수 있는지 고려해야겠다.

 

이미지 출처

[김은우의 에듀테크 트렌드 따라잡기] 코딩 교육 사이트 LeetCode가 보여주는 코딩교육의 핵심