4
/** * 有两个不同大小的二进制树： 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 * * @author Dell * */ public class Test245 { public static boolean isSubtree(TreeNode T1, TreeNode T2) { if(T2==null) return true; boolean result=false; if(T1!=null&&T2!=null) { if(T1.val==T2.val) { result=panduan(T1,T2); } if(!result) result=isSubtree(T1.left,T2); if(!result) result=isSubtree(T1.right,T2); } return result; } public static boolean panduan(TreeNode T1, TreeNode T2) { if(T2==null&&T1==null) return true; if(T2==null) return false; if(T1==null) return false; if(T1.val==T2.val) { return panduan(T1.left,T2.left)&&panduan(T1.right,T2.right); } else return false; } public static void main(String[] args) { } }
