判断二叉树是否相同/对称/子树

[metroluffy]

判断二叉树是否相同/对称

题目

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

100. 相同的树

思路

处理二叉树的问题，递归比较直观，逐级判断节点是否一致即可。

实现

const isSameTree = (p, q) => {
    if(p == null && q == null) 
        return true;
    if(p == null || q == null) 
        return false;
    if(p.val != q.val) 
        return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

也可以借助队列通过迭代来实现，每棵树分别一个队列，相同位置的节点逐级入队，再出队判断即可。

const isSameTree = (p, q) => {
    const queue1 = [];
    const queue2= [];
    queue1.push(q);
    queue2.push(p);
    while (queue1.length > 0){
        const tempQ = queue1.shift();
        const tempP = queue2.shift();
      	// 判断逻辑是一样的 
        if (tempQ === null && tempP === null) continue;
        if (tempQ === null || tempP === null) return false;
        if(tempP.val !== tempQ.val) return false;
        queue1.push(tempQ.left);
        queue1.push(tempQ.right);
        queue2.push(tempP.left);
        queue2.push(tempP.right);
    }
    return true;
}

类似的应用还有判断一棵树B是否为另一棵树A的子树，如果根节点相同则从根节点判断，如果不相同则递归判断A的左子树、右子树是否包含B。

面试题26. 树的子结构

var isSubStructure = function(A, B) {
    let result = false;
    // 边界条件，因题不同
    if(A != null && B != null){
        if(A.val  == B.val)
            result = isSameTree(A,B);
        if(!result)
            result = isSubStructure(A.left, B);
        if(!result)
            result = isSubStructure(A.right, B);
    }
    return result
};

类似的题

想到一道类似的题，检查一棵二叉树是否对称，101. 对称二叉树

const isSymmetric = root => {
    const q = [];
    q.push(root);
    q.push(root);
    while (q.length > 0) {
        const t1 = q.shift();
        const t2 = q.shift();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        q.push(t1.left);
        q.push(t2.right);
        q.push(t1.right);
        q.push(t2.left);
    }
    return true;
};

这里每次都检验对称位置的节点是否相同，然后再把其子节点按对称的顺序入队，思路上也是模拟人手工遍历。