leetcode with python:100. Same Tree

题目:

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

给定两个二元树,判断它们是否一模一样

上一题都用dfs的想法去做,所以这题我採用bfs的迴圈做法

# 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 = rightclass Solution:    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:        r1=[p]        r2=[q]        while r1!=[] and r2!=[]:            if r1[0]==None and r2[0]==None:                r1.pop(0)                r2.pop(0)                continue                        if r1[0]!=None and r2[0]==None:                return False                        if r1[0]==None and r2[0]!=None:                return False                            if r1[0].val==r2[0].val:                r1.append(r1[0].left)                r2.append(r2[0].left)                r1.append(r1[0].right)                r2.append(r2[0].right)                r1.pop(0)                r2.pop(0)            else:                return False        return True

简单来说就是一层一层全部抓出来比
有两个阵列分别储存两个树待确认的节点
由于先进先确认,储存阵列用类似queue的方式去实作
检测部分先检测含有None的几种可能
都没None的话就确认值是否一样
确认完就提出,同时将它们的left跟right放入各自的储存阵列
完全通过的话就回传True
最后执行时间32ms(faster than 89.99%)

另外这里顺便介绍在讨论区出现的简短dfs递迴解

# 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 = rightclass Solution:    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:        if p and q:            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)        return p is q

先确认两树的对应节点是否含有None
有的话则判断异同回传
无的话就判断异同同时向下探索
最后执行时间32ms(faster than 89.91%)

那我们下题见