#572另一棵树的子树

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) return true;
        if (root == null) return false;
        return same(root, subRoot)
                || isSubtree(root.left, subRoot)
                || isSubtree(root.right, subRoot);
    }

    private boolean same(TreeNode first, TreeNode second) {
        if (first == null || second == null) return first == second;
        return first.val == second.val
                && same(first.left, second.left)
                && same(first.right, second.right);
    }
}