树的子结构
欢迎关注作者简书
csdn传送门
题目
输入两颗二叉树A和B，判断B是不是A的子结构
思想
要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：第一步在树A中找到和B的根结点的值一样的结点N，第二步再判断树A中以N为根结点的子树是不是包括和树B一样的结构。
第一步在树A中查找与根结点的值一样的结点。这实际上就是树的遍历。
第二步判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点N的值和树B的根结点不相同，则以N为根结点的子树和树B肯定不具有相同的结点；如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。
源码
/**
* @program:
* @description: 输入两颗二叉树A和B，判断B是不是A的子结构
* @author: zhouzhixiang
* @create: 2018-11-10 11:59
*/
public class Test17 {
public static class BinaryTreeNode {
int data;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(int v) {
this.data = v;
}
}
public static boolean isSubTreeNode(BinaryTreeNode A, BinaryTreeNode B) {
if (A == null) return false;
if (B == null) return true;
boolean result = false;
if (A.data == B.data){
result = match(A, B);
}
if(result) return true;
return isSubTreeNode(A.left, B) || isSubTreeNode(A.right, B);
}
private static boolean match(BinaryTreeNode A, BinaryTreeNode B) {
if(A == B) return true;
if(A == null) return false;
if(B == null) return true;
if(A.data == B.data) {
return match(A.left, B.left) || match(A.right, B.right);
}
return false;
}
public static void main(String[] args) {
BinaryTreeNode root1 = new BinaryTreeNode(18);
root1.left = new BinaryTreeNode(8);
root1.right = new BinaryTreeNode(29);
root1.right.left = new BinaryTreeNode(20);
root1.right.right = new BinaryTreeNode(31);
root1.left.left = new BinaryTreeNode(5);
root1.left.left.left = new BinaryTreeNode(4);
root1.left.left.right = new BinaryTreeNode(6);
root1.left.right = new BinaryTreeNode(9);
root1.left.right.right = new BinaryTreeNode(10);
BinaryTreeNode root2 = new BinaryTreeNode(8);
root2.left = new BinaryTreeNode(5);
root2.right = new BinaryTreeNode(9);
root2.right.right = new BinaryTreeNode(10);
root2.left.left = new BinaryTreeNode(4);
root2.left.right = new BinaryTreeNode(6);
System.out.println(isSubTreeNode(root1, root2));
}
}
我们一定要注意边界条件的检查，即检查空指针。当父树或子树为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃
欢迎加入Java猿社区
欢迎加入Java猿社区.png
