输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
主要思路:
(1)在tree1中寻找tree2的根节点,如果找到了,就接着往下匹配左右节点,如果没有找到,就直接返回false,表示匹配失败;
(2)加入tree1的某个节点和tree2的根节点相等,但是左右子树并不相同,并不能说明tree2就不是tree1的子结构,应该继续往下寻找;
如上图所示,根节点1相同,但是左右子树并不相同,此时并不能说tree2不是tree1的子机构,因为在tree1的左子树中包含tree2这个结构。
思想比较简答,但是这个题感觉考得是代码的完整性和健壮性,就是对边界的判断。
主要考虑:
一、在寻找相同的根节点时:
(1)两颗树为空,直接返回false;
(2)任意一棵树为空,直接返回false;
(3)两棵树都不为空:
3.1 节点值相等,则判断节点之外的子结构;
3.2 节点值不相等,那么用tree1的当前节点的左孩子与tree2的根节点匹配;
3.3 tree1的当前节点的左孩子与tree2的根节点值不相等,用tree1的当前节点的右孩子与tree2的根节点匹配。
二、判断tree2是不是tree1的子结构
(1)tree1为空,tree2不为空,直接返回false,因为tree1的树的结构是大于等于tree2的;
(2)如果tree2为空,说明递归完成,之前的匹配都成功,直接返回true
(3)节点的值不相等,返回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){
// 如果两个数都不为空,就进行A树的遍历,寻找和B树根节点相同的节点
if(root1.val == root2.val){
result = DoseTree1HaveTree2(root1,root2);
}
// 如果跟节点不相等,则判断左子树和右子树
if(!result){
result = HasSubtree(root1.left,root2);
}
if(!result){
result = HasSubtree(root1.right,root2);
}
}
return result;
}
private boolean DoseTree1HaveTree2(TreeNode tree1,TreeNode tree2){
if(tree1 == null && tree2 != null)
return false;
if(tree2 == null)
return true;
if(tree1.val != tree2.val)
return false;
return DoseTree1HaveTree2(tree1.left,tree2.left) && DoseTree1HaveTree2(tree1.right,tree2.right);
}
}