Subtree 245
Question
You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
Notice
A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
Example
T2 is a subtree of T1 in the following case:
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
T2 isn't a subtree of T1 in the following case:
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
Solution
非递归版本:非递归版本用BFS遍历T1,找所有与T2值相等的点,作为备选节点。然后比较以这些节点为根的子树是否和T2等同。
递归版本:先看T1和T2是否等同,若不等同,则递归看T1的左右子树是否和T2等同。
代码如下:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
// write your code here
if(T2 == null){
return true;
}
if(T1 == null){
return false;
}
//非递归 Version
// Queue<TreeNode> queue = new LinkedList<TreeNode>();
// queue.offer(T1);
// TreeNode root = new TreeNode(T2.val + 1);
// ArrayList<TreeNode> candidates = new ArrayList<TreeNode>();
// while(!queue.isEmpty()){
// TreeNode curt = queue.poll();
// if(curt.val == T2.val){
// root = curt;
// candidates.add(curt);
// }
// if(curt.left != null){
// queue.offer(curt.left);
// }
// if(curt.right != null){
// queue.offer(curt.right);
// }
// }
// if(root.val != T2.val){
// return false;
// }
// for(TreeNode node : candidates){
// if(isIdentical(node, T2)){
// return true;
// }
// }
// return false;
//递归 Version
if(isIdentical(T1, T2)){
return true;
}
if(isSubtree(T1.left, T2) || isSubtree(T1.right, T2)){
return true;
}
return false;
}
private boolean isIdentical(TreeNode a, TreeNode b){
if(a == null || b == null){
return a == b;
}
if(a.val != b.val){
return false;
}
return isIdentical(a.left, b.left) && isIdentical(a.right, b.right);
}
}