地址：

 

题目大意是要求你判断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
      
       & 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
       
        & 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
        
         & v1,vector
         
          & v2){29         if(v1.size()!=v2.size()){30             return false;31         }32         else{33             for(int i=0;i
          
           val==t->val){49                 vector
           
             vf1,vf2;50 vector
            
              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 是否含有 t65 bool isSubtree(TreeNode* s, TreeNode* t) {66 bool flag=false;67 DFS(s,t,flag);68 return flag;69 }70 };
            
           
          
         
        
       
      

 

---

 

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

 

1 class Solution { 2 public: 3     // 对于一棵树，如果相等，那么该根结点相等，左子树，右子树都相等；继续递归 4     bool isEqual(TreeNode* s, TreeNode* t){ 5         if(s==NULL || t==NULL){ 6             if(s==t){ 7                 return true; 8             } 9             return false;10         }11         return s->val==t->val && isEqual(s->left,t->left) && isEqual(s->right,t->right);12     }13     14     // true条件只能通过isEqual实现; 另外这个代码的返回值非常巧妙，对于||，只需要有一个true，那么最上层的返回值一定为true15     bool isSubtree(TreeNode* s, TreeNode* t) {16         if(s==NULL){17             return false;18         }19         return isEqual(s,t) || isSubtree(s->left,t) || isSubtree(s->right,t);20     }21 };

 

 

这一比较，就发现自己对递归，对树的理解真是糟糕透顶。

 

在isSubtree中，实现了判断t是否为s的子树；

在check中，判断s和t是否相同；

 

对于s和t而言，如果t是s的子树，那么有三种可能，t和s相同，t是s左子树的子树，t是s右子树的子树； 对应： 

return check(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);

对于s和t相等，需要保证它们当前指的结点值相等以及左子树和右子树都相等；   递归终止条件为出现不相等，或者都等于NULL；

 

鶸。