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.在命中的情況下是否存在只需要檢查兩側(cè)的子樹相等這一種情況姆另，還是說存在查找？
2.在未命中的情況下是否意味著已經(jīng)不匹配了呢侣颂，還是說通過下移t可以再次匹配档桃？
這兩種答案都是肯定的，而且只在t是根節(jié)點才成立憔晒。
/**
* 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;
}
}
}
