题目描述
对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B,请返回一个bool值,代表A中是否存在一棵同构于B的子树。
代码如下:
import java.util.*; /*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
// 一个函数求两棵树是否相同(递归),另一个函数递归求一个树的子树是否和另一棵树相同
public class IdenticalTree {
public boolean chkIdentical(TreeNode A, TreeNode B) {
// write code here
//在A中找到一个节点的值等于B,如果isSameTree返回的值是正确的,就返回正确,否则接着往下找
if(A == null) return false;
if(isSameTree(A, B)) return true;
return chkIdentical(A.left, B) || chkIdentical(A.right, B);
}
public boolean isSameTree(TreeNode A, TreeNode B){
if(A == null && B == null) return true;
if(A == null || B == null) return false;
if(A.val != B.val) return false;
return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
} }