小黑leetcode之旅:100 相同的树

小黑解法:树相等=结构相等+先/中根遍历的val值相等

# 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:
        pre = []
        mid = []
        # i判断是否树的结构相等，使用先根进行标注索引i
        self.i = 0
        # 先根遍历
        def pre_node(node):
            
            if node:
                pre.append(node.val)
                # 重新赋予val值，避免val重复带来的判断失误
                node.val = self.i
                self.i += 1
                pre_node(node.left)
                pre_node(node.right)

        def mid_node(node):

             if node:
                mid_node(node.left)
                mid.append(node.val)
                mid_node(node.right)
        pre_node(p)
        mid_node(p)

        p_pre = pre[:]
        p_mid = mid[:]

        pre = []
        mid = []
        self.i= 0

        pre_node(q)
        mid_node(q)

        if p_pre == pre and p_mid == mid:
            return True
        return False

深度优先搜索

# 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:
        
        # p和q都为空的情况下
        if not p and not q:
            return True
        
        # 只有一个为空
        if not p or not q:
            return False
        
        # 全不为空的情况下
        if 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 not q:
            return True
        # 有一个为空
        if not p or not q:
            return False
        
        # 初始化队列
        queue1 = collections.deque([p])
        queue2 = collections.deque([q])
        # 开始对队列进行操作
        while queue1 and queue2:
            # 队尾出栈
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            if node1.val != node2.val:
                return False
            # 左孩子进队
            
            if node1.left and node2.left:
                queue1.append(node1.left)
                queue2.append(node2.left)
            if (not node1.left and node2.left) or (node1.left and not node2.left):
                return False

            if node1.right and node2.right:
                queue1.append(node1.right)
                queue2.append(node2.right)
            if (not node1.right and node2.right) or (node1.right and not node2.right):
                return False
        return not(queue1 or queue2)