limanting 的个人博客

题目

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

我的答案

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
var isSubStructure = function (A, B) {
    if (!B || !A) {
        return false;
    }
    const queque = [A];
    while (queque.length) {
        const nodeA = queque.shift();
        if (hasChild(nodeA, B)) {
            return true;
        }
        if (nodeA.left) {
            queque.push(nodeA.left);
        }
        if (nodeA.right) {
            queque.push(nodeA.right);
        }
    }
    return false;


};

var hasChild = function (A, B) {
    if (!B) {
        return true;
    }
    if (!A) {
        return false;
    }
    if (A.val === B.val && hasChild(A.left, B.left) && hasChild(A.right, B.right)) {
        return true;
    }
    return false;
}

这道题是广度搜索增加递归比对是否包含子树。