问题描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解决思路
首先判断B的根节点和A的根节点是否相同（这里的相同是指节点的值相同并且左右子节点相同），如果相同比较他们的左右子节点，这一步骤是相同的，可以用递归完成，直到B遍历到每个尾节点，如果这一过程比较的所有节点是相同的，则证明B是A的子结构。如果B的根节点和A的根节点不同，则A向他的左右子节点滑动，然后继续跟B的子节点比较，步骤同上。
public class Solution {
/**
* 二叉树的构造 内部类
*/
public class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val) {
this.val = val;
}
}
public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result=false;
//如果root1和root2不为null
if (root1!=null&&root2!=null){
//判断两个值是否相同
if (root1.val==root2.val){
result=isHaveTree(root1,root2);
}
if (!result){
result=HasSubtree(root1.left,root2);
}
if (!result){
result=HasSubtree(root1.right,root2);
}
}
return result;
}
public static boolean isHaveTree(TreeNode root1,TreeNode root2) {
//如果第二个节点为空 true
if (root2==null){
return true;
}
//如果第一个节点为空 false
if (root1==null){
return false;
}
//如果不同
if (root1.val!=root2.val){
return false;
}
//继续递归
return isHaveTree(root1.left,root2.left)&&isHaveTree(root1.right,root2.right);
}
}
