LeetCode 572. 另一个树的子树

地址：https://leetcode-cn.com/classic/problems/subtree-of-another-tree/description/

题目大意是要求你判断t所代表的树是否为s所代表树的子树。  

我的解题思路：

1. 既然要比较是否含有，那么肯定需要遍历，选择什么样的遍历序列？    我认为只有先序好些一点。
2. 那么对s进行先序遍历，如果此时s所指的结点的val等于t所指的结点的val，那么可以进行比较。
3. 如何判断完全相等呢？     有一个性质：通过先序遍历和中序遍历能够完全确定一棵二叉树，那么我只需要对这两棵树进行遍历，那么通过它们的遍历序列我就能够判断这两棵树是否完全相同。    

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void PreOrder(TreeNode *s,vector<int>& v){
13         if(s!=NULL){
14             v.push_back(s->val);
15             PreOrder(s->left,v);
16             PreOrder(s->right,v);
17         }
18     }
19
20     void InOrder(TreeNode *s,vector<int>& v){
21         if(s!=NULL){
22             PreOrder(s->left,v);
23             v.push_back(s->val);
24             PreOrder(s->right,v);
25         }
26     }
27
28     bool IsEqual(vector<int>& v1,vector<int>& v2){
29         if(v1.size()!=v2.size()){
30             return false;
31         }
32         else{
33             for(int i=0;i<v1.size();i++){
34                 if(v1[i]!=v2[i]){
35                     return false;
36                 }
37             }
38             return true;
39         }
40     }
41
42     // 对s进行先序遍历,如果当前结点的值和t的root的值相同，进行比对;
43     void DFS(TreeNode *s,TreeNode *t,bool& flag){
44         if(flag){
45             return ;
46         }
47         if(s!=NULL){
48             if(t!=NULL && s->val==t->val){
49                 vector<int> vf1,vf2;
50                 vector<int> vi1,vi2;
51                 PreOrder(s,vf1);
52                 PreOrder(t,vf2);
53                 InOrder(s,vi1);
54                 InOrder(t,vi2);
55                 if(IsEqual(vf1,vf2) && IsEqual(vi1,vi2)){
56                     flag=true;
57                 }
58             }
59             DFS(s->left,t,flag);
60             DFS(s->right,t,flag);
61         }
62     }
63
64     // s 是否含有 t
65     bool isSubtree(TreeNode* s, TreeNode* t) {
66         bool flag=false;
67         DFS(s,t,flag);
68         return flag;
69     }
70 };

View Code

---

然而这个效率，有点惨不忍睹。    参考一下其他人的代码：