子结构判断 中等

问题：

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：

输入：tree1 = [1,7,5], tree2 = [6,1]
输出：false
解释：tree2 与 tree1 的一个子树没有相同的结构和节点值。

示例 2：

输入：tree1 = [3,6,7,1,8], tree2 = [6,1]
输出：true
解释：tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。

回答：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function(A, B) {
    if (!B || !A) return false;
    //递归调用进行判断
    return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};
//判断两棵树是否相同
var isSameTree = function(tree1, tree2) {
    //子树tree2可以为空
    if (!tree2) {
        return true;
    }
    // 若tree2存在，但tree1为空，一定是fasle
    if (!tree1) {
        return false;
    }
    if (tree1.val != tree2.val) {
        return false;
    }
    return isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right)
}