leetcode572 另一棵树的子树

1.与100、101解法相同

递归：

class Solution {
private:bool compare(TreeNode* p, TreeNode* q){if(!p && !q) return true;else if(!p || !q) return false;else if(p->val != q->val) return false;bool leftside = compare(p->left, q->left);bool rightside = compare(p->right, q->right);bool issame = leftside && rightside;return issame;}
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(!root) return false;if(compare(root, subRoot)) return true;return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}
};

调用方式	检查范围	是否递归搜索
compare(root->left, subRoot)	仅检查 root->left 是否完全等于 subRoot	否
isSubtree(root->left, subRoot)	检查 root->left 及其所有子树是否包含 subRoot	是

1. 递归调用修正：

   • 原代码：return compare(root->left, subRoot) || compare(root->right, subRoot);

   • 修改后：return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);

   • 原因：需要使用 isSubtree 递归检查所有可能的子树，而不仅仅是直接子节点

序列化+KMP算法解法详解

这个方法通过将二叉树序列化为字符串，然后使用KMP字符串匹配算法来查找子树，是一种非常巧妙的优化解法。我将详细解释每个步骤。

1. 算法整体思路

1. 序列化两棵树：将root树和subRoot树都序列化为字符串（或数组）

2. 字符串匹配：使用KMP算法检查subRoot的序列化结果是否是root序列化结果的子串

• 前序遍历序列化：采用根-左-右的顺序序列化树结构

• 空节点表示：使用INT_MAX表示空节点（确保不会与正常节点值冲突）

class Solution {
private:void tree2array(TreeNode* node, vector<int>& seq){if(!node) {seq.push_back(INT_MAX);return;}seq.push_back(node->val);tree2array(node->left, seq);tree2array(node->right, seq);}void getnext(int* next, const vector<int>& s){next[0] = 0;int j = 0;for(int i = 1; i < s.size(); i++){while(j >= 1 && s[i] != s[j]) j = next[j-1];if(s[j] == s[i]) j++;next[i] = j;}}bool kmp(const vector<int>& s, const vector<int>& p){vector<int> next(p.size());getnext(&next[0], p);int j = 0;for(int i = 0; i < s.size(); i++){while(j > 0 && s[i] != p[j]) j = next[j-1];if(s[i] == p[j]) {j++;if(j == p.size()) return true;}    }return false;}public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {vector<int> seq_root;vector<int> seq_subRoot;tree2array(root, seq_root);tree2array(subRoot, seq_subRoot);return kmp(seq_root, seq_subRoot);}
};