题目描述

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

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

例如:
给定的树 A:

  1.  3<br />    / \<br />   4   5<br />  / \<br /> 1   2<br />给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：

0 <= 节点个数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

题目理解那里，需要注意，B不一定要完全覆盖A的节点，B可以只是A的一部分，这么理解才对。

/**
 * 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 (!A || !B) return false;

    let queue = [A];


    while (queue.length) {
        let node = queue.shift();
        // 如果两个节点值相等，则进入遍历子结构函数中。遍历完判定是，则返回true，否则继续寻找下一个相等节点进入判定
        if (node.val === B.val && travelTree(node, B)) {
            return true;
        }
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return false;
};

function travelTree(A, B) {
    // A和B全等，一般为null，或引用完全一致，则返回true
    if (A === B) return true;
    // A是null了，而B不是，则返回false
    if (A === null) return false;
    // B是null了，而A不是，则B是A的一部分，返回true
    if (B === null) return true;
    // A和B的值不相等，返回false
    if (A.val !== B.val) return false;
    // 如果A的左右子树和B的左右子树不是子结构，返回false
    if (!travelTree(A.left, B.left)) return false;
    if (!travelTree(A.right, B.right)) return false;
    return true;
}