题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
oj连接： https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
解法1
代码语言：javascript复制/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean is(TreeNode root1,TreeNode root2){
//root2等于null时，说明已经比较完了，就返回true
if(root2 ==null)
return true;
//root1等于null时，说明root2不是root1的子树，返回false
if(root1 ==null)
return false;
//如果root1和root2的值不一样，就返回false
if(root1.val != root2.val)
return false;
//如果一样，就继续比较root1和root2的左节点和右节点。
return is(root1.left,root2.left) && is(root1.right,root2.right);
}
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//如果有一个为null，就直接返回false，因为空的树，不是任何一个树的子树
if(root1 == null || root2 ==null)
return false;
boolean bool = false;
//找到相等的一个，从相等的根节点处开始比较左右子节点
if(root1.val == root2.val){
bool = is(root1,root2);
}
//如果root1,val != root2.val 那么就继续寻找左右子节点
if(bool != true)
bool = HasSubtree(root1.left,root2);
//如果还等于false，说明在left中没有找到，就继续找right
if(bool != true)
bool = HasSubtree(root1.right,root2);
return bool;
}
}
