0100：相同的树

2015-04-10 约 275 字预计阅读 1 分钟次阅读

力扣第 100 题

题目

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

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

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-10⁴ <= Node.val <= 10⁴

分析

#1

递归很容易写出。

1
2
3
4
5
6
7


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def dfs(p,q):
            if not p or not q:
                return not p and not q
            return p.val==q.val and dfs(p.left,q.left) and dfs(p.right,q.right)
        return dfs(p,q)

37 ms

#2

也可以用栈遍历判断。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        sk = [(p,q)]
        while sk:
            a,b = sk.pop()
            if not a and not b:
                continue
            if not a or not b or a.val!=b.val:
                return False
            sk.extend([(a.right,b.right),(a.left,b.left)])
        return True

34 ms

目录

0100：相同的树

题目

分析

#1

#2

解答