每日一道算法题--leetcode 100--相同的树--python

644 阅读1分钟

【题目描述】

【代码思路】

对比两棵树是否相同,我们可以想到将每棵树中所有节点都保存在一个列表当中,再对比列表即可。其实采用任意一种遍历二叉树的方式均可。

本题我们采用前序遍历的方式遍历二叉树,但是有一点不同的是,当遇到空节点的时候不能直接跳过,需要有一定标记,用于对比两棵树的节点出现的顺序以及数值是否完全相同。

python中优秀的列表拼接方式,有+,extend,和切片拼接。

【源代码】

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        return self.dfs(p)==self.dfs(q)
        
    def dfs(self,root):
        if root:
            return [root.val]+self.dfs(root.left)+self.dfs(root.right)
        else:
            return [None]