이진트리 자료구조 풀이 (동일한 트리)#1

이진 트리 문제 풀이(동일 트리 확인)

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

문제 설명

2개의 트리가 주어지고, 서로 같은 구조의 노드들이 같은 값을 가지는 동일한 트리인지 확인하는 문제입니다.

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.

문제 해석 및 풀이 방향!

• 트리 문제는 보통 재귀를 사용해서 푼다고 하기에, 재귀를 이용해서 노드의 끝까지 탐색
• 노드의 구조와 노드의 값을 비교하면서 재귀를 실행
• 양쪽 끝까지 도달하면 true 반환
• 중간에 구조가 다르면 false 반환
• 중간에 노드의 값이 다르더라도 false 반환

코드

• 위의 방향성을 가지고 아래의 코드로 만들었습니다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    // 두 개의 트리가 끝까지 같을 때 문제없이 실행되어 아무 노드도 남지 않았을 경우 true
    if (!p && !q) {
        return;
    }

    // 양쪽에 있는 노드들의 값을 비교하고 구조도 확인
    // 노드 구조가 다르거나 값이 다르면 false로 조기 return
    if (!p || !q || p.val !== q.val) {
        return false;
    }

    // 왼쪽을 계속 확인하고, 오른쪽을 계속 확인
    isSameTree(p.left, q.left) && isSameTree(p.right, p.right);
};

느낀 점

• 이진 트리라는 것을 처음으로 공부해 보고, 조금 간단해 보이는 문제를 찾았는데도 접근하기가 어려웠습니다.
• 조금 더 익숙해질 필요가 있고, 다른 트리 문제들도 접해 봐야 할 것 같습니다.