# 【基础篇 - Day 14】 2020-11-14 - 100. 相同的树（03. 树 ）
# 题目描述
输入: 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 (!p && !q) return true
if (!p || !q) return false
if (q.val != p.val) return false
return isSameTree(q.left, p.left) &&
isSameTree(q.right, p.right)
};
# 解法二
时间复杂度：O(n)
空间复杂度: O(2n)
层序遍历
var isSameTree = function (p, q) {
if (!p && !q) return true
if (!p || !q) return false
let PStack = [p]
let QStack = [q]
while (PStack.length) {
const Pcurr = PStack.shift()
const Qcurr = QStack.shift()
console.log(Pcurr, Qcurr)
if (Pcurr.val === Qcurr.val) {
if (Pcurr.left && Qcurr.left) {
PStack.push(Pcurr.left)
QStack.push(Qcurr.left)
} else if (!Pcurr.left && !Qcurr.left) {
} else if (!Pcurr.left || !Qcurr.left) {
return false
}
if (Pcurr.right && Qcurr.right) {
PStack.push(Pcurr.right)
QStack.push(Qcurr.right)
} else if (!Pcurr.right && !Qcurr.right) {
} else if (!Pcurr.right || !Qcurr.right) {
return false
}
} else {
return false
}
}
return true
}
# 解法三
时间复杂度：O(n)
空间复杂度: O(n)
优化成一个栈 看着舒服了，从内存消耗上看 没有减少= =
var isSameTree = function (p, q) {
let Stack = [{ p, q }]
while (Stack.length) {
const { p: currP, q: currQ } = Stack.shift()
console.log(currQ, currP)
if (!currP && !currQ) continue
if (!currP || !currQ) return false
if (currP.val !== currQ.val) return false
Stack.push({
p: currP.left,
q: currQ.left
})
Stack.push({
p: currP.right,
q: currQ.right
})
}
return true
}
https://github.com/leetcode-pp/91alg-2/issues/39#issuecomment-727695908