LeetCode 572. 另一个树的子树

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

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

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

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

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

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

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

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

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

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

鶸。

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

发表评论

表情：
评论列表 （有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

    相关 572. 另一个树的子树

    给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

    骑猪看日落骑猪看日落/ 0 赞/ 120 阅读

    相关 572. 另一个树的子树

    > 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子

    心已赠人心已赠人/ 0 赞/ 470 阅读

    相关 LeetCode572. 另一个树的子树

    给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

    迷南。迷南。/ 0 赞/ 242 阅读