没有问题，但是不是最优的题解

两年前做过这道题目，这次发现不会做了，一直没有想到合适的解法（其实有一点思路，但是不会写），然后查看题解，也看了一下之前自己的题解，没有发现正确答案。其中一个反例：root2如果是root1的叶子节点（也就是一个只有根节点的二叉树），其中root1的深度大于等于3，那么其他答案的结果返回false，实际上应该是true。
我的解法：获取所有节点，依次判断是否是子结构。
不足：这块是有多余的判断，应该可以优化，正确的题解应该跟dfs或者dp有关，主要优化点在于保存已校验的状态

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null)
            return false;
        //遍历root1
        Stack<TreeNode> stack = new Stack<>();
        getTreeNodes(root1, stack);
        while (!stack.isEmpty()) {
            boolean flag = hasSubtree(stack.pop(), root2);
            if (flag) {
                return flag;
            }
        }
        return false;
    }

    private void getTreeNodes(TreeNode root, Stack<TreeNode> stack) {
        if (root == null){
            return;
        }
        stack.push(root);
        getTreeNodes(root.left, stack);
        getTreeNodes(root.right, stack);
    }

    public boolean hasSubtree(TreeNode root1, TreeNode root2) {
        if (root2 == null)
            return true;
        if (root1 == null)
            return false;
        boolean b = root1.val == root2.val;
        return b && hasSubtree(root1.left, root2.left) && hasSubtree(root1.right,root2.right);
    }