思路
递归三要素
1、递归出口:最简单的情况,树高为1
2、分解子问题:求左子树、右子树情况
3、父问题与子问题的交集
代码
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
复杂度
时间复杂度:o(n),n为节点个数
空间复杂度:o(h),h为树高度