我正在查看 LeetCode 問題“ 100. Same Tree ”：
給定兩個二叉樹 p 和 q 的根，撰寫一個函式來檢查它們是否相同。
如果兩個二叉樹在結構上相同并且節點具有相同的值，則它們被認為是相同的。
我的代碼通過了一些測驗用例，而另一些則失敗了。
我的具體問題是測驗用例[1,2] and [1,null,2]。PythonNone不使用null. 當我使用本地代碼編輯器（Visual Studio 代碼）時，它會產生預期的輸出。我知道我可以用其他方式實作它，但我不明白為什么這個解決方案不適用于 LeetCode。
這是我的代碼：
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
answer1 = []
answer2 = []
self.helperFunction(p, q, answer1, answer2)
for i in range(len(answer1)):
if answer1[i] != answer2[i]:
return False
return True
def helperFunction(self, p, q, answer1, answer2):
if p != None and q != None:
self.helperFunction(p.left, q.left, answer1, answer2)
answer1.append(p.val)
answer2.append(q.val)
self.helperFunction(p.right, q.right, answer1, answer2)
uj5u.com熱心網友回復：
您的代碼假定兩棵樹具有相同的形狀。但是，如果一棵樹有一個子樹而另一棵樹沒有，則您的代碼永遠不會訪問該子樹，當樹的其余部分相同時，這將給出誤報。僅僅存在這樣一個孩子（在另一棵樹中不存在）就足以表明中止該程序并回傳 False。
至于演算法本身。很遺憾你這樣做：
answer1.append(p.val)
answer2.append(q.val)
...當您實際上可以立即比較這兩個值時（而不是在最后這樣做）。為什么不檢查一下p.val == q.val，如果不是這樣，請停止進一步尋找？另一方面，如果它們相等，也沒有理由將這些值附加到串列中。它只是意味著“到目前為止一切都很好”，你可以繼續......
結論：
- 兩邊都沒有節點時回傳 True (
None) - 當一側的節點不在另一側時，回傳 False
- 對應節點的值不同時回傳 False
- 當且僅當遞回也為兩個孩子都回傳 True 時才回傳 True。
實施的：
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return bool(not p and not q or
p and q and p.val == q.val and self.isSameTree(p.left, q.left)
and self.isSameTree(p.right, q.right))
uj5u.com熱心網友回復：
讓我們看看以下輸入的“answer1”和“answer2”變數：
輸入：
[1,2] [1,null,2]
輸出：
答案 1 = 答案 2 = [1]
如您所見，一旦您的 helperFunction 中的值“p”或“q”之一為空，您的程式就會錯誤地停止比較兩棵樹的節點。這是由于以下代碼行：
if p != None and q != None:
對您的錯誤的簡單修復可能是這樣的：
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
answer1 = []
answer2 = []
self.helperFunction(p, q, answer1, answer2) # changed
return answer1 == answer2
def helperFunction(self, p, q, answer1, answer2):
if p != None and q != None:
self.helperFunction(p.left, q.left, answer1, answer2)
self.helperFunction(p.right, q.right, answer1, answer2)
if p is None:
answer1.append(None)
else:
answer1.append(p.val)
if q is None:
answer2.append(None)
else:
answer2.append(q.val)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/486306.html