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.
翻译：检查一棵树t是否是另外一棵树s的子树。
这题是很好的一题。有很多问题值得细细考虑的。
记s.val==t.val为命中，相反为未命中。
那么，
1.在命中的情况下是否存在只需要检查两侧的子树相等这一种情况，还是说存在查找？
2.在未命中的情况下是否意味着已经不匹配了呢，还是说通过下移t可以再次匹配？
这两种答案都是肯定的，而且只在t是根节点才成立。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
return isSub(s,t,t);
}
private boolean isSub(TreeNode s, TreeNode t,TreeNode tRoot)
{
if(s==null||t==null)
{
if(t==null&&s==null)
return true;
else
return false;
}
if(s.val==t.val)
{
if(t==tRoot)
return isSub(s.left,t.left,tRoot)&&isSub(s.right,t.right,tRoot)||
isSub(s.left,t,tRoot)||isSub(s.right,t,tRoot);
else
return isSub(s.left,t.left,tRoot)&&isSub(s.right,t.right,tRoot);
}
else
{
if(t==tRoot)
return isSub(s.left,t,tRoot)||isSub(s.right,t,tRoot);
else
return false;
}
}
}
