【LeetCode刷题之路】剑指Offer26.树的子布局

LeetCode刷题纪录

   

• 🌐 我的博客主页：iiiiiankor
  
• 🎯 假如你以为我的内容对你有资助，不妨点个赞👍、留个批评✍，大概收藏⭐，让我们一起进步！
  
• 📝 专栏系列：LeetCode 刷题日记
  
• 🌱 文章内容来自我的学习与实践履历，假如你有任何想法或标题，接待随时在批评区互换讨论。让我们一起探索更多的大概！🚀
  

  

标题形貌

输入两棵二叉树A和B，判断B是不是A的子布局。(约定空树不是恣意一个树的子布局)
B是A的子布局， 即 A中有出现和B雷同的布局和节点值。
比方:

1. 给定的树 A:
2.      3
3.     / \
4.    4   5
5.   / \
6. 1   2
8. 给定的树 B：
9.    4
10.   /
11. 1

复制代码

返回 true，由于 B 与 A 的一个子树拥有雷同的布局和节点值。
示例 1：

1. 输入：A = [1,2,3], B = [3,1]
2. 输出：false

复制代码

示例 2：

1. 输入：A = [3,4,5,1,2], B = [4,1]
2. 输出：true

复制代码

留意

• 0 <= 节点个数 <= 10000
  

思绪

标题让判断B是不是A的子布局
但是我们举行判断是基于 两个树的根相称时, 去判断是否为子布局
针是否即是B的根节点的值对A做先序遍历的过程中 假如根节点雷同我们去判断此时B是不是以该根节点的子树的子布局!
实际上举行先序遍历的同时要举行递归判断子布局

• B是不是A节点的子布局
  
• B是不是A的左子树的子布局
  
• B是不是A的右子树的子布局
  

实际上2和3就是在举行先序遍历！
因此须要借助辅助函数, hasSub(A,B)
该函数是用于判断,B是不是以A为根节点的树的子布局。假如A,B值不等，直接返回false

代码

1. class Solution {
2. public:
3.     //B是不是以A为根节点的子结构
4.     bool hasSub(TreeNode* A,TreeNode* B){
5.         //既然是从A中找B的结构
6.         //如果B是空 或者 A和B同时为空,说明B走完了 A中有B的结构
7.         if(!B)  return true;
8.         if(!A)  return false;
9.         if(A->val != B->val){
10.             return false;
11.         }
12.         //判断B的左子树是不是A的左子树的子结构
13.         //B的右子树是不是A的右子树的子结构
14.         return hasSub(A->left,B->left) && hasSub(A->right , B->right);
15.     }   
16.     //isSubStructure实际上是进行先序遍历！！！
17.     bool isSubStructure(TreeNode* A, TreeNode* B) {
18.         //如果B是空树，谁的子结构也不是
19.         //如果A走到空树，说明没有与A匹配的子结构 返回false
20.         if(B==NULL || A==NULL){
21.             return false;
22.         }
23.         //B是A的子结构 有三种情况
24.         //A和B根相同,判断B是不是A的子结构
25.         //B是A的左子树的子结构
26.         //B是A的右子树的子结构
27.                 //
28.         return hasSub(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B) ;
29.     }
30. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金