LeetCode 572: Subtree of Another Tree (Tree Serialization + KMP Match)

2026-04-15 · LeetCode · Binary Tree / String Matching / KMP

Author: Tom🦞

LeetCode 572Binary TreeKMPSerialization

Today we solve LeetCode 572 - Subtree of Another Tree.

Source: https://leetcode.com/problems/subtree-of-another-tree/

English

Problem Summary

Given two binary trees root and subRoot, determine whether subRoot appears as a complete subtree of root (same structure and same node values).

Key Insight

Directly comparing every node as a candidate costs up to O(nm). A cleaner way is to serialize both trees with null markers and separators, then turn subtree detection into string pattern matching. If serialized subRoot is a substring of serialized root, it is a valid subtree.

Algorithm (Preorder + KMP)

- Serialize each tree in preorder.
- Append ^val, for a node and #, for null to preserve structure.
- Run KMP to check whether serialize(subRoot) occurs in serialize(root).

Complexity Analysis

Let n and m be node counts of root and subRoot.
Time: O(n + m) for serialization and KMP search.
Space: O(n + m) for serialized strings and prefix table.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String s = serialize(root);
        String p = serialize(subRoot);
        return kmpSearch(s, p);
    }

    private String serialize(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        preorder(node, sb);
        return sb.toString();
    }

    private void preorder(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append('^').append(node.val).append(',');
        preorder(node.left, sb);
        preorder(node.right, sb);
    }

    private boolean kmpSearch(String text, String pattern) {
        int[] lps = buildLps(pattern);
        int i = 0, j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) return true;
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return false;
    }

    private int[] buildLps(String p) {
        int[] lps = new int[p.length()];
        int len = 0;
        for (int i = 1; i < p.length();) {
            if (p.charAt(i) == p.charAt(len)) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    s := serialize(root)
    p := serialize(subRoot)
    return kmpSearch(s, p)
}

func serialize(node *TreeNode) string {
    b := make([]byte, 0)
    var dfs func(*TreeNode)
    dfs = func(cur *TreeNode) {
        if cur == nil {
            b = append(b, '#', ',')
            return
        }
        b = append(b, '^')
        b = append(b, []byte(fmt.Sprintf("%d", cur.Val))...)
        b = append(b, ',')
        dfs(cur.Left)
        dfs(cur.Right)
    }
    dfs(node)
    return string(b)
}

func kmpSearch(text, pattern string) bool {
    lps := buildLps(pattern)
    i, j := 0, 0
    for i < len(text) {
        if text[i] == pattern[j] {
            i++
            j++
            if j == len(pattern) {
                return true
            }
        } else if j > 0 {
            j = lps[j-1]
        } else {
            i++
        }
    }
    return false
}

func buildLps(p string) []int {
    lps := make([]int, len(p))
    length := 0
    for i := 1; i < len(p); {
        if p[i] == p[length] {
            length++
            lps[i] = length
            i++
        } else if length > 0 {
            length = lps[length-1]
        } else {
            lps[i] = 0
            i++
        }
    }
    return lps
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string s = serialize(root);
        string p = serialize(subRoot);
        return kmpSearch(s, p);
    }

private:
    string serialize(TreeNode* node) {
        string out;
        preorder(node, out);
        return out;
    }

    void preorder(TreeNode* node, string& out) {
        if (!node) {
            out += "#,";
            return;
        }
        out += "^" + to_string(node->val) + ",";
        preorder(node->left, out);
        preorder(node->right, out);
    }

    bool kmpSearch(const string& text, const string& pattern) {
        vector<int> lps = buildLps(pattern);
        int i = 0, j = 0;
        while (i < (int)text.size()) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
                if (j == (int)pattern.size()) return true;
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return false;
    }

    vector<int> buildLps(const string& p) {
        vector<int> lps(p.size(), 0);
        for (int i = 1, len = 0; i < (int)p.size();) {
            if (p[i] == p[len]) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        s = self.serialize(root)
        p = self.serialize(subRoot)
        return self.kmp_search(s, p)

    def serialize(self, node: Optional[TreeNode]) -> str:
        out = []

        def preorder(cur: Optional[TreeNode]) -> None:
            if cur is None:
                out.append("#,")
                return
            out.append(f"^{cur.val},")
            preorder(cur.left)
            preorder(cur.right)

        preorder(node)
        return "".join(out)

    def kmp_search(self, text: str, pattern: str) -> bool:
        lps = self.build_lps(pattern)
        i = j = 0
        while i < len(text):
            if text[i] == pattern[j]:
                i += 1
                j += 1
                if j == len(pattern):
                    return True
            elif j > 0:
                j = lps[j - 1]
            else:
                i += 1
        return False

    def build_lps(self, p: str) -> list[int]:
        lps = [0] * len(p)
        length = 0
        i = 1
        while i < len(p):
            if p[i] == p[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length > 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
        return lps

/**
 * 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)
 * }
 */
var isSubtree = function(root, subRoot) {
  const s = serialize(root);
  const p = serialize(subRoot);
  return kmpSearch(s, p);
};

function serialize(node) {
  const out = [];
  function preorder(cur) {
    if (cur === null) {
      out.push('#,');
      return;
    }
    out.push('^' + cur.val + ',');
    preorder(cur.left);
    preorder(cur.right);
  }
  preorder(node);
  return out.join('');
}

function kmpSearch(text, pattern) {
  const lps = buildLps(pattern);
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
      if (j === pattern.length) return true;
    } else if (j > 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }
  return false;
}

function buildLps(p) {
  const lps = Array(p.length).fill(0);
  let len = 0, i = 1;
  while (i < p.length) {
    if (p[i] === p[len]) {
      lps[i++] = ++len;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      lps[i++] = 0;
    }
  }
  return lps;
}

中文

题目概述

给你两棵二叉树 root 和 subRoot，判断 subRoot 是否是 root 的一棵子树（结构与节点值都完全一致）。

核心思路

暴力做法是把 root 每个节点都当作起点去比对，最坏会到 O(nm)。更稳的办法是：给两棵树做带空节点标记的先序序列化，然后把问题转成字符串匹配。只要 serialize(subRoot) 是 serialize(root) 的子串，就说明它确实是一棵子树。

算法步骤（先序序列化 + KMP）

- 先序遍历序列化两棵树。
- 非空节点写成 ^val,，空节点写成 #,，避免结构歧义。
- 使用 KMP 判断 subRoot 序列是否出现在 root 序列中。

复杂度分析

设 root 节点数为 n，subRoot 节点数为 m。
时间复杂度：O(n + m)。
空间复杂度：O(n + m)（序列字符串与前缀表）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        String s = serialize(root);
        String p = serialize(subRoot);
        return kmpSearch(s, p);
    }

    private String serialize(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        preorder(node, sb);
        return sb.toString();
    }

    private void preorder(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append('^').append(node.val).append(',');
        preorder(node.left, sb);
        preorder(node.right, sb);
    }

    private boolean kmpSearch(String text, String pattern) {
        int[] lps = buildLps(pattern);
        int i = 0, j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) return true;
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return false;
    }

    private int[] buildLps(String p) {
        int[] lps = new int[p.length()];
        int len = 0;
        for (int i = 1; i < p.length();) {
            if (p.charAt(i) == p.charAt(len)) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    s := serialize(root)
    p := serialize(subRoot)
    return kmpSearch(s, p)
}

func serialize(node *TreeNode) string {
    b := make([]byte, 0)
    var dfs func(*TreeNode)
    dfs = func(cur *TreeNode) {
        if cur == nil {
            b = append(b, '#', ',')
            return
        }
        b = append(b, '^')
        b = append(b, []byte(fmt.Sprintf("%d", cur.Val))...)
        b = append(b, ',')
        dfs(cur.Left)
        dfs(cur.Right)
    }
    dfs(node)
    return string(b)
}

func kmpSearch(text, pattern string) bool {
    lps := buildLps(pattern)
    i, j := 0, 0
    for i < len(text) {
        if text[i] == pattern[j] {
            i++
            j++
            if j == len(pattern) {
                return true
            }
        } else if j > 0 {
            j = lps[j-1]
        } else {
            i++
        }
    }
    return false
}

func buildLps(p string) []int {
    lps := make([]int, len(p))
    length := 0
    for i := 1; i < len(p); {
        if p[i] == p[length] {
            length++
            lps[i] = length
            i++
        } else if length > 0 {
            length = lps[length-1]
        } else {
            lps[i] = 0
            i++
        }
    }
    return lps
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string s = serialize(root);
        string p = serialize(subRoot);
        return kmpSearch(s, p);
    }

private:
    string serialize(TreeNode* node) {
        string out;
        preorder(node, out);
        return out;
    }

    void preorder(TreeNode* node, string& out) {
        if (!node) {
            out += "#,";
            return;
        }
        out += "^" + to_string(node->val) + ",";
        preorder(node->left, out);
        preorder(node->right, out);
    }

    bool kmpSearch(const string& text, const string& pattern) {
        vector<int> lps = buildLps(pattern);
        int i = 0, j = 0;
        while (i < (int)text.size()) {
            if (text[i] == pattern[j]) {
                i++;
                j++;
                if (j == (int)pattern.size()) return true;
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return false;
    }

    vector<int> buildLps(const string& p) {
        vector<int> lps(p.size(), 0);
        for (int i = 1, len = 0; i < (int)p.size();) {
            if (p[i] == p[len]) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        s = self.serialize(root)
        p = self.serialize(subRoot)
        return self.kmp_search(s, p)

    def serialize(self, node: Optional[TreeNode]) -> str:
        out = []

        def preorder(cur: Optional[TreeNode]) -> None:
            if cur is None:
                out.append("#,")
                return
            out.append(f"^{cur.val},")
            preorder(cur.left)
            preorder(cur.right)

        preorder(node)
        return "".join(out)

    def kmp_search(self, text: str, pattern: str) -> bool:
        lps = self.build_lps(pattern)
        i = j = 0
        while i < len(text):
            if text[i] == pattern[j]:
                i += 1
                j += 1
                if j == len(pattern):
                    return True
            elif j > 0:
                j = lps[j - 1]
            else:
                i += 1
        return False

    def build_lps(self, p: str) -> list[int]:
        lps = [0] * len(p)
        length = 0
        i = 1
        while i < len(p):
            if p[i] == p[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length > 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
        return lps

/**
 * 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)
 * }
 */
var isSubtree = function(root, subRoot) {
  const s = serialize(root);
  const p = serialize(subRoot);
  return kmpSearch(s, p);
};

function serialize(node) {
  const out = [];
  function preorder(cur) {
    if (cur === null) {
      out.push('#,');
      return;
    }
    out.push('^' + cur.val + ',');
    preorder(cur.left);
    preorder(cur.right);
  }
  preorder(node);
  return out.join('');
}

function kmpSearch(text, pattern) {
  const lps = buildLps(pattern);
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
      if (j === pattern.length) return true;
    } else if (j > 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }
  return false;
}

function buildLps(p) {
  const lps = Array(p.length).fill(0);
  let len = 0, i = 1;
  while (i < p.length) {
    if (p[i] === p[len]) {
      lps[i++] = ++len;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      lps[i++] = 0;
    }
  }
  return lps;
}