【Leetcode】100 : 相同的树(Python)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【Leetcode】100 : 相同的树(Python)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1686字，纯文字阅读大概需要3分钟。

内容图文

题目：

给定两个二叉树，编写一个函数来检验它们是否相同。

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

题目解析：

方法一：

这个题目很明显就可以用递归来做，有关树的题目用递归来做基本上是我们需要想到的首选！如果两个树是相同的，我们只需要比较其树根是相同的，同时递归调用比较树根的下一级子树是相同的，那么则可以得到整个树的结构是相同的，我自己的方法如下：

# 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 p==q==None:
            return True
        if q==None or p==None:
            return False
        if p.val==q.val:
            pleft=p.left
            pright=p.right
            qleft=q.left
            qright=q.right
            if self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right):
                return True

首先是设定递归的条件，然后在一级一级向下比较就可以了，思想和之前《剑指offer》当中的镜像二叉树的思想是相同的，后来发现自己第二步在进行递归的时候写多余了，没必要将树再往下推一步然后递归，可以直接进行递归，因此修改后如下：

# 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 p==q==None:
            return True
        if q==None or p==None:
            return False
        if p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right):
            return True

这样两个if可以合并成一个if语句，减少了时间复杂度，同时也不需要再进行遍历到下一级之后再做递归，最后的成绩如下：

 后来看了看其他人用java语言/go语言刷这道题的方法也基本这样，也就没必要再想迭代解法了。

内容总结

以上是互联网集市为您收集整理的【Leetcode】100 : 相同的树(Python)全部内容，希望文章能够帮你解决【Leetcode】100 : 相同的树(Python)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端