。。。剑指Offer之——树的子结构。。。
1 // 遍历整个树 2 public boolean HasSubtree(TreeNode root1, TreeNode root2) { 3 boolean result = false; 4 // 如果root1,root2中只要有一个是null,则返回false 5 if (root1 != null && root2 != null) { 6 // 找到两个数值相同的根节点 7 if (root1.val == root2.val) { 8 // 判断以这个根节点的子树，是否包含root2 9 result = doesTree1HasTree2(root1, root2); 10 } 11 // 如果不包含，则继续到root1的左边去查找与root2根结点相同的节点 12 if (!result) { 13 result = HasSubtree(root1.left, root2); 14 } 15 // 如果不包含，则继续到root1的右边去查找与root2根结点相同的节点 16 if (!result) { 17 result = HasSubtree(root1.right, root2); 18 } 19 } 20 return result; 21 } 22 23 public boolean doesTree1HasTree2(TreeNode root1, TreeNode root2) { 24 // 如果子树为空，则返回true 25 if (root2 == null) { 26 return true; 27 } 28 // 走到这里，说明root2不为空，而如果roo1为空，则返回false 29 if (root1 == null) { 30 return false; 31 } 32 // 走到这里，说明root1，root2均不为空，判断它们的值是否相等 33 if (root1.val != root2.val) { 34 return false; 35 } 36 // 如果root1的值=root2的值，则递归判断root1的左边和root2的做左边 37 // 如果root1的值=root2的值，则递归判断root1的右边和root2的做右边 38 return doesTree1HasTree2(root1.left, root2.left) && 39 doesTree1HasTree2(root1.right, root2.right); 40 }
更多精彩
