572. Subtree of Another Tree
Given two non-empty binary trees s and t , check whether tree t has exactly the same structure and node values with a subtree of s . A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
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 .
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
/*
问题：判断某子树是否是主树的子结构
方法：前序遍历的递归方法
主树s， 子树t
*/
class Solution
{
public :
bool isSubtree ( TreeNode * s , TreeNode * t ) //遍历主树s（前序遍历递归法）
{
if ( s == nullptr ) return false ; //前序遍历递归的出口， 注意一定要加判断空指针的语句，后面有s->left和s->right
//前序遍历（递归法）主树t各结点,从根结点到左子树再到右子树（s一直在延伸，展开分支）
if ( isSame ( s , t )) //判断当前结点下的子树是否一样
return true ;
else //判断当前结点的左子树是否为子树t,再判断右子树是否为子树t
return isSubtree ( s -> left , t ) || isSubtree ( s -> right , t );
}
private :
bool isSame ( TreeNode * s , TreeNode * t ) //确定s父结点后，开始同时扫描（递归法）s和t，看是各个结点是否相等
{
if ( s == nullptr && t == nullptr ) return true ; //如果最后均遍历到空结点，返回true
else if ( s == nullptr || t == nullptr ) return false ; //如果一个遍历到空，一个没有，说明不同，返回false
if ( s -> val == t -> val )
{
return isSame ( s -> left , t -> left ) && isSame ( s -> right , t -> right );
}
else
return false ; //不相同，返回假
}
};