이진트리 자료구조 풀이 (동일한 트리)#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;
}

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

// 왼쪽 쭈욱 확인 ,오른쪽 쭈욱 확이
isSameTree(p.left, q.left) && isSameTree(p.right, p.right);
};

느낀점

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