剑指offer - 树的子结构(Java实现)

题目链接：https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&&tqId=11170&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路：1、我们判断B树是否是以A树当前结点为顶点的子树，如果是则返回true；2、否则说明当前A树所在的节点不是B树的顶点，我们可以使用前序遍历找到B树在A树上面的顶点，然后在去判断其子结构。
  当我们找到B树在A树上的顶点以后进入判断子结构函数，我们需要判断的左子树和右子树也是子结构就需要使用递归，当B树为空的时候说明前面的所有情况都相等，此时就是递归的出口，当B树为空，A树不为空时，此时B树一定不是A树的子结构。

/**
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) {
        if(root1 == null || root2 == null) return false;
        return dfs(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }
    public boolean dfs(TreeNode root1,TreeNode root2) { //判断子结构
        if(root2 == null) return true;
        if(root1 == null) return false;
        if(root1.val != root2.val) return false;
        return dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
    }
}