LintCode2016年8月8日算法比赛----子树

子树

题目描述

有两个不同大小的二叉树：T1有上百万的节点；T2有好几百的节点。请设计一种算法，判定T2是否为T1的子树。

注意事项

若 T1 中存在从节点 n 开始的子树与 T2 相同，我们称 T2 是 T1 的子树。也就是说，如果在T1节点n处将树砍
断，砍断的部分将与T2完全相同。

样例

下面的例子中 T2 是 T1 的子树：

   		 1                3
  		/               / 
  T1 = 2   3      T2 =  4
      /
   	 4

下面的例子中T2不是T1的子树：

         1               3
  		/                
  T1 = 2   3       T2 =    4
      /
     4

算法分析：

前面一道题目是判断两棵二叉树是否相等，可以直接利用前面的算法，将T1的所有子树与T2进行比较即可。

Java算法实现：

/**
 * 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
       boolean result=false;
		if(T2==null){
			return true;
		}
		else{
			
			if(T1!=null){
				result=isIdentical(T1, T2);
				if(!result){
					result=isSubtree(T1.left, T2);
					if(!result){
						result=isSubtree(T1.right, T2);
					}
				}
			}
			return result;
		}
    }
    
    public static  boolean isIdentical(TreeNode a, TreeNode b) {
        // Write your code here
		if(a==null&&b==null){
			return true;
		}
		else if(a==null||b==null){
			return false;
		}
		else{
			if(a.val!=b.val){
				return false;
			}
			else{
				boolean result=isIdentical(a.left, b.left);
				if(!result){
					return result;
				}
				else{
					result=isIdentical(a.right, b.right);
					return result;
				}
			}
		}
    }
}