共计 1658 个字符,预计需要花费 5 分钟才能阅读完成。
1. 问题描述
输入两棵二叉树 A,B,判断 B 是不是 A 的子结构。(ps:我们约定空树不是任意一个树的子结构)
2. 思路
首先根据题目,只有两个树都不为 null 时才需要进行判断,否则直接返回 false。
然后就是遍历大树,找小树的头节点,如果遍历完都没找到,就是 false
如果找到小树的头节点,就依次比较后面对应的左右子节点,如果有一个不相等就是 false,
一一对应到最后时,肯定是小树的节点为 null,大树不一定为 null,所以先用小树判断。
如果大树为 null 了,小树还不是,说明小树不是大树的子结构,返回 false。
我觉得难的是遍历大树过程中左子树遍历完成后如何回到根节点,这里使用两个方法,在第二个方法中进行递归遍历根节点一侧的子树,遍历完成后就可以再第一个方法中返回到根节点了。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {this.val = val;}
}
*/
public class Solution {public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false; // 用来记录判断结果
if(root1 != null && root2 != null){ // 只有两个根节点都不为 null 时才进行判断,否则直接返回 false。result = doesTree1HaveTree2(root1,root2); // 调用 doesTree1HaveTree2 方法判断 Tree2 是不是 Tree1 的子结构
if(!result){ // 当前两个根节点的值不相等就判断 root1 的左子节点是否和 root2 节点相等
result = doesTree1HaveTree2(root1.left,root2);
}
if(!result){ //root1 的左子树的节点都和 root2 不等的情况下判断 root1 的右子树节点和 root2 是不是相等。result = doesTree1HaveTree2(root1.right, root2);
}
}
return result; //root1 都遍历完成后返回结果。}
public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2){if(node2 == null){ // 如果 node2 树先遍历完了都和 node1 对上,说明 node2 是 node1 的子结构返回 true
return true;
}
if(node1 == null){ // 如果 node2 不为 null 而 node1 为 null 了说名 node2 不是 node1 的子结构,返回 false
return false;
}
if(node1.val != node2.val){ // 只要判断过程中有一个不想等直接返回 false,这里注意只是判断一个子树没有匹配的,在 HasSubTree 中还会判断右子树中是否存在 root2 结构,所以不会漏掉。return false;
}
return doesTree1HaveTree2(node1.left, node2.left) && doesTree1HaveTree2(node1.right, node2.right);
// 当前节点的值相等,判断左右两个子节点的值是不是相等,有一个不等就返回 false。}
}
注意:
(1)doesTree1HaveTree2 方法中判断小树是否为 null 必须放在前面,不能和判断大树是否为 null 交换,因为如果换了的话,在大树为 null 时,小树不确定,小树如果也为 null,就应该是 true,而这时返回的是 false,就是错误的。(2) 如果根节点的左子树中有小树的一部分,而右子树中有整个小树,这种情况不会漏掉,因为在 HasSubTree 方法中是先判断左子树,在判断右子树,左子树返回 false 时,会在右子树中重新找小树的根节点,所以不会漏掉。
参考
Boooobby 的牛客网答案
正文完