[LeetCode] The Same Tree

문제 링크

Can you solve this real interview question? Same Tree - 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: [https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg] Input: p = [1,2,3], q = [1,2,3] Output: true Example 2: [https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg] Input: p = [1,2], q = [1,null,2] Output: false Example 3: [https://assets.leetcode.com/uploads/2020/12/20/ex3.jpg] 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]. * -104 <= Node.val <= 104

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

문제 요구 조건

두개의 이진 트리가 동일한지 확인하는 문제에요.

나의 문제 풀이

재귀적으로 접근하는 방식을 써야겠다고 생각했지만, 풀지는 못했어요. ㅠ 바로 풀이로 가실게요.

정답 문제 풀이

이 문제를 풀기 위해서는 재귀적 방법으로 푸는 것이 추천되어요. 일단 둘다 null인 경우 / 하나만 null인 경우 / 노드값이 다른 경우를 먼저 커버한 다음에 재귀적 함수를 사용하면 되어요.

정답 풀이

TypeScript
/**
 * 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) {
    // 1. 두 노드가 모두 null이면 동일
    if (!p && !q) {
        return true;
    }

    // 2. 둘 중 하나만 null이거나, 두 노드의 값이 다르면 동일하지 않음
    if (!p || !q || p.val !== q.val) {
        return false;
    }

    // 3. 왼쪽 서브트리와 오른쪽 서브트리가 모두 동일한지 재귀적으로 확인
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

코드를 설명해 볼게요.

isSameTree(p, q) 함수는 두 개의 노드를 인자로 받아요.

첫 번재 if 문

p와 q가 모두 null 인 경우를 체크합니다. 이는 두 트리의 해당 위치가 모두 비어있으면 동일하다고 판단하여 true를 반환하게 할거에요

두 번째 if문

여기서는 세가지의 경우를 한 번에 처리할거에요.

!p 또는 !q

p와 q 중 하나만 null 인 경우 (위의 첫 번쨰 if 문에서 둘 다 null 인 경우는 이미 걸러졌겠죠?)

p.val !== q.val

두 노드가 존재하더라도 그 값이 다른 경우를 검증해요

위 조건중 하나라도 만족하면 false를 반환하게 할 거에요

마지막 return 문

두 노드가 모두 존재하고 값도 같은 경우, p의 왼쪽 자식과 q의 왼쪽 자식을 비교하는 재귀호출과 오른쪽 자식들을 비교하는 재귀호출의 결과를 AND 연산으로 결합해요. 그리고 두 서브트리가 모두 동일해야만 전체 트리가 동일하다고 판단을 할 수 있어요.

느낀점

이진 트리문제는 그렇게 어렵지 않게 느껴지면서도 머리속에 떠오르지 않아 계속 해메게 되는 문제인거 같아요. 일단 제가 이때까지 생각해보지 못한 새로운 사고방식을 적용한다는 느낌이 들어서, 못 풀면서도 이해하는 과정에서 실력을 키울 수 있다고 생각해요.

다들 오늘도 화이팅!!