Subtree of Another Tree

EasyTreeDepth-First SearchString MatchingBinary TreeHash Function

Solution

Solution1: DFS

import { TreeNode } from '@algorithm/lib';
 
export function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  if (root === null) {
    return false;
  }
  return (
    isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
  );
}
 
function isSameTree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  if (root === null || subRoot === null) {
    return root === subRoot;
  }
  return (
    root.val === subRoot.val &&
    isSameTree(root.left, subRoot.left) &&
    isSameTree(root.right, subRoot.right)
  );
}

Complexity

  • Time: O(m⋅n)O(m \cdot n)
    • m: root 트리의 노드 개수, n: subRoot 트리의 노드 개수
  • Space: O(h)O(h)
    • h: root 트리의 높이. 만약, 한 쪽으로 편향된 트리라면 최대 O(n)O(n)이 될 수 있습니다.

Solution2: KMP

주어진 트리를 문자열로 바꿔서, KMP 알고리즘을 사용하여, subRoot의 패턴이 있는지 확인하는 방법입니다.

import { TreeNode } from '@algorithm/lib';
 
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  return kmpSearch(serialize(root), serialize(subRoot));
}
 
function serialize(root: TreeNode | null): string {
  if (root === null) {
    return ',#';
  }
  return `,${root.val}${serialize(root.left)}${serialize(root.right)}`;
}
 
function buildLPS(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let [i, matched] = [1, 0];
  while (i < pattern.length) {
    if (pattern[i] === pattern[matched]) {
      matched += 1;
      lps[i] = matched;
      i += 1;
    } else {
      if (0 < matched) {
        matched = lps[matched - 1];
      } else {
        lps[i] = 0;
        i += 1;
      }
    }
  }
  return lps;
}
 
function kmpSearch(text: string, pattern: string): boolean {
  const lps = buildLPS(pattern);
  let [i, j] = [0, 0];
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i += 1;
      j += 1;
    }
    if (j === pattern.length) {
      return true;
    }
    if (i < text.length && text[i] !== pattern[j]) {
      if (0 < j) {
        j = lps[j - 1];
      } else {
        i += 1;
      }
    }
  }
  return false;
}

Complexity

  • Time: O(m+n)O(m + n)
  • Space: O(m+n+h)O(m + n + h)
LeetCode
Subtree of Another Tree
https://leetcode.com/problems/subtree-of-another-tree