题目描述

[EN | CN]

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

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

示例 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:递归

做法很简单了,在每次比较两个结点的时候,先比较自身,再往下递归比较。

假设二叉树结点数为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(\log_2n)$,递归深度为树的高度。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# 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 not (p and q):
            return False
        return (p.val == q.val
            and self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )
  • 执行用时:36 ms,在所有 Python3 提交中击败了 82.48% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 7.14% 的用户。