题目描述：题目传送门
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
判断B是不是A的子树 —-> A中包含B的结构
- 我们遍历二叉树A的节点，直到找到与二叉树根节点的值相同为止
- 然后再比较该节点下的子节点是不是和二叉树B的子节点的值相同
- 如果不是，那我们接着遍历A树，找出下一个与B树根节点值相同的节点
- 重复2、3步骤直到遍历完A树或B树
代码
public class Solution {
// 查询A树中是否包含B树的根节点
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null) return false;
if (root2 == null) return false;
// 最后的结果
boolean res = false;
// 找到值相同的节点
if (root1.val == root2.val) {
// 继续判断B树的子节点与A树子节点是否值相等
res = JudgeTree(root1, root2);
}
// 向左搜索
if (!res) {
res = HasSubtree(root1.left, root2);
}
// 向右搜索
if (!res) {
res = HasSubtree(root1.right, root2);
}
return res;
}
// 判断B树中根节点外的子节点是否也在A树中
public boolean JudgeTree(TreeNode root1, TreeNode root2) {
// B树遍历结束，说明A树包含B树
if (root2 == null) return true;
// A树遍历结束，没有发现B树的结构
if (root1 == null) return false;
// 该节点的值不相等，继续寻找
if (root1.val != root2.val) return false;
// 比较A/B两树左右节点的值
return JudgeTree(root1.right, root2.right) && JudgeTree(root1.left, root2.left);
}
}
样例：
TreeNode root1 = new TreeNode(1); TreeNode r11 = new TreeNode(5); TreeNode r12 = new TreeNode(3); TreeNode r13 = new TreeNode(7); TreeNode r14 = new TreeNode(5); TreeNode r15 = new TreeNode(7); TreeNode r16 = new TreeNode(6); root1.left = r11; root1.right = r12; r11.left = r13; r12.left = r14; r14.right = r16; r14.left = r15; TreeNode root2 = new TreeNode(5); TreeNode r21 = new TreeNode(7); TreeNode r22 = new TreeNode(6); root2.left = r21; root2.right = r22; System.out.println(HasSubtree(root1, root2)); //A树 1 5 3 7 5 7 6 //B树 5 7 6