572.subtree-of-another-tree.md

572. Subtree of Another Tree

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
        3
       / \
      4   5
     / \
    1   2

    4
   / \
  1   2
Output: true

Input: 
        3
       / \
      4   5
     / \
    1   2

    4
   / \
  1   3
Output: false

Edge / Corner Cases

• One of the trees is empty.
• The two trees are the same.
• It contains the subtree but with more nodes.

Input: 
        1
      /   \
     2     3
    / \     \
   4   5     6
  /
 7

    2
   / \
  4   5
Output: false, there is [7] in the tree but not in the subtree.

DFS

fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
    if (root == null && subRoot == null) return true
    if (root == null || subRoot == null) return false

    return isSameTree(root, subRoot) || isSubtree(root?.left, subRoot) || isSubtree(root?.right, subRoot)
}

private fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
	// Use the same implementation as [100. Same Tree](../leetcode/100.same-tree.md)
}

• Time Complexity: O(m * n), where m and n represents the nodes of two trees, we have to traverse the tree (isSubtree()) and compare the nodes in the subtree (isSameTree()).
• Space Complexity: O(max(m, n)), the space is used for recursion call stack when traversing the tree.

KMP

We can serialize the tree by DFS, then use KMP to find the subtree in the tree. Here we have to add the specific value for null node to avoid the ambiguity of the serialization.

TODO: https://leetcode.cn/problems/subtree-of-another-tree/solutions/233896/ling-yi-ge-shu-de-zi-shu-by-leetcode-solution/