1. 题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
2. 题目分析
两颗二叉树A和B，右边的树B是左边树A的子结构
- 要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：
a. 第一步，在树A种找到和树B的根节点的值一样的节点R；
b. 第二步，判断树A中以R为根节点的子树是不是包括和树B一样的结构。 - 以上面的两棵树来分析这个过程。首先试着在树A中找到值为8（树B的根节点的值）的节点。从树A的根节点开始遍历，我们发现树A的根节点就是8,。接着判断树A根节点的左子树和右子树是不是和树B的左子树和右子树一样。
- 此题中可知，根节点的左子树和右子树并不一样。仍需要遍历树A，接着继续查找值为8的节点。我们在树A的第二层找到了一个数值为8的节点，然后进行第二步的判断，既判断这个节点下面的子树是不是和树B一样的结构。
3. 题目代码
public class Solution { public static boolean HasSubtree(TreeNode root1, TreeNode root2) { boolean a = false; if(root1 != null && root2 != null){ if(root1.val == root2.val){ a = Tree(root1,root2); } if(!a){ a = HasSubtree(root1.left,root2); } if(!a){ a = HasSubtree(root1.right,root2); } } return a; } public static boolean Tree(TreeNode root1, TreeNode root2){ if(root2 == null){ return true; } if(root1 == null){ return false; } if(root1.val != root2.val){ return false; } return Tree(root1.left,root2.left) && Tree(root1.right,root2.right); } }
