大家好，又见面了，我是全栈君。
来自《剑指offer》的面试题18。
题目：输入两棵二叉树A和B，推断B是不是A的子结构。二叉树节点定义例如以下：
代码语言：javascript复制public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}思路分析：
首先，在Tree1中找到和Tree2的根节点的值一样的结点R。
然后，再推断Tree1中以R为根结点的子树是不是包括和Tree2一样的结构。
分析演示样例：
解决思路代码：
这里两处推断均使用了递归。详见代码。
代码语言：javascript复制public class Solution {
public boolean HasSubtree(TreeNode root1, TreeNode root2) { // 在Tree1中查找是否有Tree2的根节点（实际上就是树的遍历）
boolean result = false;
if (root1 != null && root2 != null) { // 边界条件的检查
if (root1.val == root2.val) {
result = DosTree1HasTree2(root1, root2);
}
if (!result) {
result = HasSubtree(root1.left, root2);
}
if (!result) {
result = HasSubtree(root1.right, root2);
}
}
return result;
}
public boolean DosTree1HasTree2(TreeNode root1, TreeNode root2) { // 推断Tree1中以R为根节点的子树是不是和树B具有同样的结构（即左右子树是否同样）
if (root2 == null) { // 递归终止条件到达了Tree1或Tree2的叶节点。
return true;
}
if (root1 == null) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return DosTree1HasTree2(root1.left, root2.left)
&& DosTree1HasTree2(root1.right, root2.right); // 递归推断左右子树
}
}測试代码：
代码语言：javascript复制// 进行測试
public class Main {
Scanner scanner = new Scanner(System.in);
public TreeNode createTree(TreeNode root) {
String val = scanner.next();
if (val.equals("#")) {
return null;
}
root = new TreeNode(Integer.parseInt(val));
root.left = createTree(root.left);
root.right = createTree(root.right);
return root;
}
public static void main(String[] args) {
TreeNode root1 = null;
TreeNode root2 = null;
Main testMain = new Main();
Solution testSolution = new Solution();
boolean result = false;
System.out.println("Create Tree 1:");
root1 = testMain.createTree(root1);
System.out.println("Create Tree 2:");
root2 = testMain.createTree(root2);
result = testSolution.HasSubtree(root1, root2);
System.out.println("The result is: " result);
}
}測试数据为： 8 8 9 # # 2 4 # # 7 # # 7 # # 8 9 # # 2 # #
执行结果：
牛客网測试地址：http://www.nowcoder.com/books/coding-interviews/6e196c44c7004d15b1610b9afca8bd88?rp=1
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/116419.html原文链接：https://javaforall.cn
