【力扣572】另一颗树的子树

题目

思路

1. 递归
2. 迭代，使用前序或者后序遍历将两棵树的节点储存在容器中，注意因为题目性质，需要子树完成相等而不是一部分相等，所以需要将每个叶节点的空孩子也表示出来；不能使用中序遍历，使用中序遍历的时候，错误如下:

== 子树根节点的右树的最左节点作为左树最右节点的后节点会造错误==

• code(迭代)

class Solution {
public:vector<int> vec;vector<int> nexts;bool isSubtree(TreeNode* root, TreeNode* subRoot) {process(root);vector<int> root_vec = vec;vec.clear();process(subRoot);vector<int> sub_vec = vec;get_nexts(sub_vec);int ptr1 = 0;int ptr2 = 0;while(ptr1 < root_vec.size() && ptr2 < sub_vec.size()){if(root_vec[ptr1] == sub_vec[ptr2]){ptr1++;ptr2++;}else if(ptr2==0)ptr1++;elseptr2 = nexts[ptr2];}return ptr2 == sub_vec.size();}void get_nexts(vector<int> vec){int L = vec.size();if(L<1)return;nexts.resize(L+1);nexts[0] = -1;nexts[1] = 0;int cur_idx = 2;int cm = nexts[cur_idx-1];while(cur_idx<=L){if(vec[cm] == vec[cur_idx-1])nexts[cur_idx++] = ++cm;else if(cm>0)cm = nexts[cm];else    nexts[cur_idx++] = 0;}return;}void process(TreeNode* root){   if(root==nullptr){vec.push_back(INT_MAX);return;}vec.push_back(root->val);process(root->left);process(root->right);return;}