leetcode_深度搜索和广度搜索 100. 相同的树

100. 相同的树

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

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

• 思路: (递归法)

  • 返回True的情况:
    • 两棵树都为空
    • 两棵树相同
  • 返回False的情况:
    • 两棵树不为空但节点分布不同或节点值不同不相同
    • 两棵树有一个为空
  • 注: 先判断是否为空, 再判断节点值是否相同

- # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSameTree(self, p, q):""":type p: Optional[TreeNode]:type q: Optional[TreeNode]:rtype: bool"""if not p and not q:# 如果p,q都为空,返回Truereturn Trueelif not p or not q:# 如果p,q其中之一为空,返回Falsereturn Falseelif p.val != q.val:# 如果根节点值不同,返回Falsereturn Falseelse:# 调用自身分别对p,q两树的左子树和右子树进行判别return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)      

• 时间复杂度: O(n)
• 空间复杂度: O(h),h是树的高度