/*
* 二叉树结点类
*/
class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

/*
* @param {Node} 节点1
* @param {Node} 节点2
* @return {Boolean} 树2是否是树1的子结构
*/
function isSubTree(node1, node2) {
    let result = false
    if (node1 && node2) {
        if (node1.value === node2.value) { // 若是节点的值相同
            result = doesNode1HasNode2(node1, node2) // 判断后面的子节点结构是否相同
        }
        if (!result) { // 若是根节点的值不同, 则用树1的左子树遍历
            result = isSubTree(node1.left, node2)
        }
        if (!result) { // 用树1的右子树遍历
            result = isSubTree(node1.right, node2)
        }
    }
    return result
}
/*
* node2是否是node1的子树: node1和node2的根节点的值是否相同
* @param {Node} 节点1
* @param {Node} 节点2
* @return {Boolean} 树2是否是树1的子结构
*/
function doesNode1HasNode2(node1, node2) {
    if (!node2) { // 若是node2全遍历完了则说明node1包含node2
        return true
    }
    // 若是node1遍历完了 或者 两个节点的值不相同
    if (!node1 || node1.value !== node2.value) {
        return false
    }
    // 节点的左子树和右子树都得相同
    return (
        doesNode1HasNode2(node1.left, node2.left) &&
        doesNode1HasNode2(node1.right, node2.right)
    )
}
const tree1 = new Node(0, new Node(1, new Node(3)), new Node(2));
const tree2 = new Node(1, new Node(3));
console.log(isSubTree(tree1, tree2));