题目名称:树的子结构
题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
分析:
第一想法是递归,只要是树,我就上递归。分析情况有以下3种:
-
当前
root1
节点=当前root2
节点 -
当前
root1
节点!=当前root2
节点,但是root1.left
和root2
节点相等 -
当前
root1
节点!=当前root2
节点,但是root1.right
和root2
节点相等
所以需要一个辅助函数helper
public static boolean hasSubtree(TreeNode root1, TreeNode root2) {
if (root1==null || root2==null) return false;
//三种情况
return helper(root1,root2) || hasSubtree(root1.left, root2) || hasSubtree(root1.right,root2);
}
//递归检查
public static boolean helper(TreeNode root1, TreeNode root2){
if (root2==null) return true;
if (root1==null) return false;
if (root1.val==root2.val)return helper(root1.left,root2.left)&&helper(root1.right,root2.right);
return false;
}
总结
遇到二叉树,递归总没错