0100-Same Tree(相同的树)

喜欢ヅ旅行 2022-09-14 11:06 145阅读 0赞

> 这个系列算是出于个人兴趣开的一个新坑吧，最近看到同学刷LeetCode算法题，就想写写那些可以一行Python代码写出来的题目，因此本专栏的文章的解题方式效率不做保证，只为追求“一行的浪漫”。

## 题目 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZGo5YWI5qOu54ix5ZCD57Sg_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 题解 ##

给你两棵二叉树的根节点 `p` 和 `q` ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。**本题难度为Easy。**

我们可以理解，根据base case，两个二叉树相同的条件为：两棵树都非空+根节点值相同+左子树相同+右子树相同。需要注意特判条件，如果两棵树都是空树那么必然相同；如果两棵树其中只有一棵树为空树那么必不相同。

## 代码 ##

实现上我们可以通过递归来进行深度优先搜索，实现整个树的判断。

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

提交的反馈如下。

![在这里插入图片描述][b3b9b9b2601f4ccfb2b69ea52c7300da.png_pic_center]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZGo5YWI5qOu54ix5ZCD57Sg_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/d1b178097be64a91bdfad098fc3da379.png
[b3b9b9b2601f4ccfb2b69ea52c7300da.png_pic_center]: /images/20220828/79344996eaf44e879ee792a846599e1b.png