【Leetcode】100 : 相同的樹(Python)-有解無憂

題目：

給定兩個二叉樹，撰寫一個函式來檢驗它們是否相同，

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，

題目決議：

方法一：

這個題目很明顯就可以用遞回來做，有關樹的題目用遞回來做基本上是我們需要想到的首選！如果兩個樹是相同的，我們只需要比較其樹根是相同的，同時遞回呼叫比較樹根的下一級子樹是相同的，那么則可以得到整個樹的結構是相同的，我自己的方法如下：

# 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語言刷這道題的方法也基本這樣，也就沒必要再想迭代解法了，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144599.html

標籤：其他

上一篇：F2. Same Sum Blocks (Hard) 決議(思維、前綴和、貪心)

下一篇：Applying heap to find median in a stream