首先根据题目,只有两个树都不为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的牛客网答案