572. Subtree of Another Tree

QUESTION:

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

EXPLANATION:

1.判断是否有相等的根节点，如果根节点相等，那么久继续判断是否是相等的树。

SOLUTION:

``````public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
queue.push(s);
while (!queue.isEmpty()){
TreeNode tmp = queue.poll();
if(tmp.val == t.val){
if(isSubtreeHelper(tmp,t))
return true;
}
if(tmp.left!=null)
queue.push(tmp.left);
if(tmp.right!=null)
queue.push(tmp.right);
}
return false;
}

public static boolean isSubtreeHelper(TreeNode s,TreeNode t){
queue.push(s);
while (!queue.isEmpty()|| !otherQueue.isEmpty()){
TreeNode tmp = queue.poll();
TreeNode oTmp = otherQueue.poll();
if ((tmp != null && oTmp == null) || (tmp == null && oTmp != null) || tmp.val != oTmp.val)
return false;
if(tmp.left!=null)
queue.push(tmp.left);
if(tmp.right!=null)
queue.push(tmp.right);

if(oTmp.left!=null)
otherQueue.push(oTmp.left);
if(oTmp.right!=null)
otherQueue.push(oTmp.right);

}
return true;
}
}
``````
>