本文最后更新于:2024年7月6日 早上
问题描述
每日一题:leetcode:100. 相同的树
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
1 2 3 4 5 6 7
| 输入: 1 1 / \ / \ 2 3 2 3
[1,2,3], [1,2,3]
输出: true
|
示例 2:
1 2 3 4 5 6 7
| 输入: 1 1 / \ 2 2
[1,2], [1,null,2]
输出: false
|
示例 3:
1 2 3 4 5 6 7
| 输入: 1 1 / \ / \ 2 1 1 2
[1,2,1], [1,1,2]
输出: false
|
题解
1 2 3
| > 类型:DFSF分制 > Time Complexity O(N) > Space Complexity O(h)
|
在每一层先检查再递归,所以这是pre-order的思路。
比对相等的条件:
p.val == q.val
if not p or not q: return p == q
如有不等,直接返回False,就不用继续递归了。最后左右孩子返回给Root:return left and right
p.s. 上面的第二个相等条件,检查了2种情况:
1.if not p and not q: return True
2.if not p or not q: return False
- 递归
1 2 3 4 5 6 7 8
| class Solution(object): def isSameTree(self, p, q): if not p or not q: return p == q if p.val != q.val: return False left = self.isSameTree(p.left, q.left) right = self.isSameTree(p.right, q.right) return left and right
|
- stack(DFS iteratively)
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution2: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: stack = [(p, q)] while stack: p, q = stack.pop() if not p and not q: continue elif (not q or not p) or (p.val != q.val): return False stack.extend([(q.right, p.right), (q.left, p.left)]) return True
|
- queue(BFS iteratively)
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution3: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: queue = collections.deque([p, q]) while queue: p, q = queue.popleft() if not p and not q: continue elif (not p or not q) or (p.val != q.val): return False queue.extend([(p.left, q.left), (p.right, q.right)]) return True
|