目录

题目solution_1solution_1参考资料

题目

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

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

示例 1:

输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: 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

solution_1

思路：递归

结果：执行用时：32 ms 排名：战胜98.8%

代码如下

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True if p and q and p.val==q.val: return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) return False

solution_1

思路：迭代

结果：执行用时：32 ms 排名：战胜98.8%

代码如下

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: stack = [(p,q)] while stack: a,b = stack.pop() if not a and not b: continue if a and b and a.val == b.val: stack.append((a.left,b.left)) stack.append((a.right,b.right)) else: return False return True

参考资料

相同的树