【leetcode】100. 相同的树（python）深度优先 + 广度优先

方法一：深度优先搜索（递归）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        elif p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

方法二：广度优先搜索（层次遍历，队列）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 广度优先搜索
        if (not p and q) or (p and not q):
            return False
        if not p and not q:
            return True
        que1, que2 = [p], [q]
        while que1:
            cur_p = que1.pop(0)
            cur_q = que2.pop(0)
            if cur_p.val != cur_q.val:
                return False
            # “A,B有一个为真,但不同时为真” 的运算称作异或^,但是用^报错呢，还是自己写把
            if (cur_p.left == None and cur_q.left != None) or (cur_p.left != None and cur_q.left == None): 
                return False
            if (cur_p.right != None and cur_q.right == None) or (cur_p.right == None and cur_q.right != None):
                return False

            if cur_p.left:
                que1.append(cur_p.left)
                que2.append(cur_q.left)
            if cur_p.right:
                que1.append(cur_p.right)
                que2.append(cur_q.right)

        return True

广度优先参考了官方题解，这里贴一下python版本的，详解请移步官方题解