[LeetCode/JAVA] 100. Same Tree

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/same-tree/

문제 설명

출처 : LeetCode

두 이진트리가 주어집니다.
주어진 두 개의 트리가 동일한 트리인지 반환하세요.

풀이 방법

Stack을 활용하여 풀이하였습니다.

주석에 코드 설명을 기록해놨습니다.

내 코드(JAVA)

 

public class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 모두 null이면 true
        if(p == null && q == null) return true;
        // 위에서 모두 null이 아님을 확인했으니, 하나라도 null이면 false
        if(p == null || q == null) return false;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(p);
        stack.push(q);

        while(!stack.isEmpty()) {
            TreeNode p1 = stack.pop();
            TreeNode p2 = stack.pop();

            // 값이 다르면 당연히 false
            if(p1.val != p2.val) return false;

            // 좌측 자식노드가 존재하면 넣음
            // 트리 모두 존재해야하므로 삽입 후 스택의 크기로 검증
            if(p1.left != null) stack.push(p1.left);
            if(p2.left != null) stack.push(p2.left);
            // 홀수면 한쪽 트리에만 들어간 것
            if(stack.size() % 2 != 0) return false;

            // 우측도 위와 동일
            if(p1.righ != null) stack.push(p1.right);
            if(p2.right != null) stack.push(p2.right);
            if(stack.size() % 2 != 0) return false;
        }

        return true;
    }

}

 

지금 보니 TreeNode 변수명을 조금 명확하게 변경하면 더 좋을 것 같습니다.

 

다른 사람 코드

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;
}

 

재귀를 이용한 방법인데, 코드를 보면 간단하지만 쉽사리 떠오르지 않습니다. 😂

 

코드 출처 : https://leetcode.com/problems/same-tree/discuss/32687/Five-line-Java-solution-with-recursion