【Day 14 】2021-05-23 - 100. 相同的树

题目描述

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
输出: true

示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

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

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(1)

递归 把几种特殊情况判断下即可

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

解法二

时间复杂度：O(n)

空间复杂度: O(2n)

层序遍历

var isSameTree = function (p, q) {
    if (!q && !p) return true
    if (!q || !p) return false
 
    let PStack = [p]
    let QStack = [q]
    while (PStack.length || QStack.length) {
        let pPop = PStack.pop()
        let qPop = QStack.pop()
        if (pPop.val !== qPop.val) return false
        if (pPop.left && qPop.left) {
            PStack.push(pPop.left)
            QStack.push(qPop.left)
        }
        else if (!pPop.left && !qPop.left) { }
        else if (!pPop.left || !qPop.left) return false
 
        if (pPop.right && qPop.right) {
            PStack.push(pPop.right)
            QStack.push(qPop.right)
        } else if (!pPop.right && !qPop.right) {
 
        } else if (!pPop.right || !qPop.right) return false
    }
    return true
};

参考回答

• 官方题解
• 精选题解