题目描述
给定两个非空的二叉树s和t，检查树t的结构和节点值是否和s的一个子树完全相同。s的子树是由s中的一个节点和该节点的所有后代组成的树（一直到根节点）。树S也可以被认为是它自己的子树。
输入实例
Example 1:
Given tree s:3/ \4 5/ \1 2
Given tree t:4 / \1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:3/ \4 5/ \1 2/0
Given tree t:4/ \1 2
Return false.
解题分析
判断是否为子树根据定义我们可以分成两部分：
1、第一步，在树A中寻找到和树B的根节点一样的节点R
2、第二步，判断在树A中以R为根节点的子树是不是包含和树B完全一样的结构
我们采用递归的策略去查找根节点和其相同的子结构，具体的实现步骤结合下面的代码体会一下。
主要代码c++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSubtree(TreeNode* s, TreeNode* t) {
bool result = false;if (s!=nullptr && t!=nullptr){
if(s->val == t->val)result = Tree1haveTree2(s,t);if(!result)result = isSubtree(s->left,t);if(!result)result = isSubtree(s->right,t);}return result;}
private:bool Tree1haveTree2(TreeNode* s, TreeNode* t){
if(t==nullptr&&s==nullptr) // 注意这里和剑指offer的不同return true;if(s==nullptr ||t==nullptr ) // 任意一个树先出现空则视为不同return false;if(s->val != t->val)return false;return Tree1haveTree2(s->left,t->left)&&Tree1haveTree2(s->right,t->right);}
};
总结
这题和剑指offer上的 【剑指offer】面试题26 树的子结构相似，唯一的不同就是，在判定子结构的方式有不同，本题中必须要完全一致（即从根节点匹配后到叶子结点必须完全一致，不能是B为在A中某非叶子节点区域内的一部分）
子结构：只要某区域内匹配即可。
子树：从匹配点到叶子结点完全匹配才算是一个子树。