LeetCode 572. 另一个树的子树

谁践踏了优雅 2023-08-17 16:55 56阅读 0赞

地址：[https://leetcode-cn.com/classic/problems/subtree-of-another-tree/description/][https_leetcode-cn.com_classic_problems_subtree-of-another-tree_description]

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

我的解题思路：

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 };

--------------------

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

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，那么最上层的返回值一定为true
    15     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；

鶸。

转载于:https://www.cnblogs.com/yy-1046741080/p/11578957.html

[https_leetcode-cn.com_classic_problems_subtree-of-another-tree_description]: https://leetcode-cn.com/classic/problems/subtree-of-another-tree/description/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/b6e3b0e13071477eb03f4718a4e69287.png