100. Same Tree

LeetCode Link (opens in a new tab)

Tree DFS

Description

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 cases

Example 1:

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

Example 2:

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

Example 3:

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].
$-10^4 <=$ Node.val $<= 10^4$

Approach

Tree는 재귀적 접근 방법으로 간단하게 해결할 수 있다.
두 트리의 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 탐색하며 두 트리의 노드 값이 같은지 확인한다.
DFS로 탐색하는 노드가 null일 때까지 재귀를 반복하고, 만약 탐색 중간에 두 노드의 값이 다르거나, 두 노드 중 하나만 null인 경우가 나타나면 false를 반환한다.
모든 탐색이 끝날 때까지 false가 반환되지 않으면 두 트리는 같은 트리이다.
Tree의 순회는 모든 노드를 한번씩 탐색하면 되기 때문에 $O(n)$ 의 시간복잡도를 갖는다.

Solution Code

var isSameTree = function(p, q) {
    const searchTree = (aTree, bTree) => {
      if (!aTree && !bTree) {
        return true
      }
 
      if (aTree && !bTree || !aTree && bTree) {
        return false
      }
 
      if (aTree.val !== bTree.val) {
        return false
      }
 
      return searchTree(aTree.left, bTree.left) && searchTree(aTree.right, bTree.right)
    }
 
    return searchTree(p, q)
};

Complexity

time complexity : $O(n)$
space complexity : $O(1)$

Intro 202. Happy Number