100 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

题解

和对称二叉树类似，我们可以利用二叉树的后序遍历来解答。

递归的三部曲（来自程序员卡尔），递归的参数，递归的终止条件以及递归的单层逻辑

递归的参数，返回值是boolean类型

递归的终止条件

var isSameSingle = function(p, q) {
    if (!p && !q) {
        //都是空，合法
        return true
    } else if((p && !q) || (!p && q)) {
        //只有一个为空
        return false
    } else if(p.val !== q.val) {
        return false
    }
    //如果还是相同，那要递归了
}

递归的逻辑

递归的逻辑就是同时看两颗树的左子树是否一样，并且右子树是否一样。

var isSameTreeLeft = isSameTree(p.left, q.left)
var isSameTreeRight = isSameTree(p.right, q.right)

return isSameTreeLeft && isSameTreeRight

整体上来说，代码如下

var isSameTree = function(p, q) {
    if (!p && !q) {
        //都是空，合法
        return true
    } else if((p && !q) || (!p && q)) {
        //只有一个为空
        return false
    } else if(p.val !== q.val) {
        return false
    }
    var isSameTreeLeft = isSameTree(p.left, q.left)
    var isSameTreeRight = isSameTree(p.right, q.right)

    return isSameTreeLeft && isSameTreeRight
}

非递归方法

同样，我们可以利用队列或者栈来实现。类似于前序遍历实现后序遍历那种。

const isSameTree = function(p, q) {
    const queue = []
    //var result = true
    queue.push(p)
    queue.push(q)

    while(queue.length) {
        const currentP = queue.shift()
        const currentQ = queue.shift()

        if(!currentP && !currentQ) {
            //继续循环
            continue;
        }

        //和上面一样判断逻辑
        if((currentP && !currentQ) || (!currentP && currentQ)) {
            //只有一个为空
            return false
        } else if(currentP.val !== currentQ.val) {
            return false
        }
        
        // 先左子树入队列
        queue.push(currentP.left)
        queue.push(currentQ.left)

        // 后右子树入队列
        queue.push(currentP.right)
        queue.push(currentQ.right)
    }

    return true
}