C/C++描述 LeetCode 572. 另一个树的子树

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客，B站昵称为：亓官劼，地址为亓官劼的B站

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

题目

难度 简单

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

示例 1:
给定的树 s:

     3     /     4   5   /   1   2 

给定的树 t：

   4    /   1   2 

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

     3     /     4   5   /   1   2     /    0 

给定的树 t：

   4   /   1   2 

返回 false。

题解

  这题是一个树的题目，让我判断树t是否是s的一个子树。这里需要我们注意一下示例2的情况，就是子树要完全相等，而不是中间的一部分相等就可以了。这题我们需要分两个递归来进行写，第一个递归进行一个结点的移动，第二个递归进行一个判断，判断是否是两个相同的树，当我们判断出有一个子树的时候，便可直接进行一个返回。

完整的题解代码为：

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  * };  */ class Solution { public: bool isSubtreeMatch(TreeNode* s, TreeNode* t){ // 进行对当前结点的树进行判断，如果两个数完全相同，则返回true，否则返回false // 如果t，s都为空时，返回true if(!s && !t) return true; // 如果（s不为空，t为空） （s不为空，t为空） （s和t的值不同） 则返回false，即他们不是完全相同的两个树 if ((s && !t) || (!s && t) || (s->val != t->val)) return false; // 递归的进行判断 return isSubtreeMatch(s->left, t->left) && isSubtreeMatch(s->right, t->right); } bool isSubtree(TreeNode* s, TreeNode* t) { // 进行移动当前结点 if (!s) return false; return isSubtreeMatch(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t); } }; 

执行效率

  这题也有一些其他的方法进行进一步的优化他的时间复杂度和空间复杂度，有兴趣的小伙伴们可以自行去优化，这里可以提供一个思路：例如树的哈希。有兴趣的小伙伴们自己去进行优化吧！

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客，B站昵称为：亓官劼，地址为亓官劼的B站

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！