我正在做 Leet Code 問題572。另一棵樹的子樹：
鑒于兩個二進制樹樹根
root和subRoot，回傳true是否有子樹root具有相同的結構和節點值subRoot和false其他。二叉樹的子樹
tree是由一個節點tree和該節點的所有后代組成的樹。這棵樹tree也可以被認為是它自己的子樹。
我有一個可行的解決方案。但是，在嘗試稍微不同的方法時，我的遞回 dfs 函式遇到了問題。我的代碼結構是這樣的：
def isSubTree(self, root, subRoot):
def dfs(root, subRoot):
# some function that returns True when certain conditions are met
if not root: return
self.isSubtree(root.left, subRoot)
self.isSubtree(root.right, subRoot)
if root.val == subRoot.val:
if dfs(root, subRoot):
return True
return False
基本上，isSubTree探索樹中的所有節點。一旦它找到具有相同的值作為節點subRoot，它比較在含有根的子樹節點為根的子樹subRoot用dfs()。
我打算當dfs()函式回傳真時，isSubTree()也將回傳真。如果我已經探索了樹中的所有節點（isSubTree()到達末尾）并且dfs()根本沒有回傳 true，isSubTree()則將回傳 False。
但是，我的代碼似乎總是回傳 false，因為它回傳的最后一行False（我已經測驗過它并且可以驗證return Trueif中的部分是否dfs()已到達，我也很確定我的dfs()函式是正確的）。
我的問題是，有沒有一種優雅的方式讓我的代碼做我想做的事？
uj5u.com熱心網友回復：
很難看出您使用的是哪個代碼，因為顯然在def dfs. 縮進關閉或缺少代碼（在撰寫本文時）。
有這些問題：
self.isSubTree根本不使用任一遞回呼叫的回傳值。這不可能是正確的，因為您當然需要這些資訊來總結已完成的作業。if not root: return當它啟動時不會回傳一個布林值。這應該區分 where alsosubTreeis的情況None：在這種情況下，回傳的值應該是True. 否則應該是False假設您未提供的
dfs代碼是正確的，它也會很好地處理前一點（其中一個或兩個引數為None），并將正確比較節點值，因此if not root不應在dfs呼叫之前執行，因為dfs將照顧那個。同樣
if root.val == subTree.val不應該出現在它現在出現的地方，而只出現在dfs.
最后，作業代碼可能是這樣的：
class Solution(object):
def isSubtree(self, root, subRoot):
def dfs(root, subRoot):
if not root or not subRoot or root.val != subRoot.val:
return root == subRoot # Must both be None to have success
return dfs(root.left, subRoot.left) and dfs(root.right, subRoot.right)
return dfs(root, subRoot) or root and (
self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
)
uj5u.com熱心網友回復：
用以下方法解決了它：
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def dfs(r1, r2):
# some function
if not root:
return False
if root.val == subRoot.val:
if dfs(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
uj5u.com熱心網友回復：
據我了解，True如果dfs()回傳True至少一個遞回分支，您希望 isSubTree 回傳。
如果分支之一找到解決方案，您將需要該isSubTree函式立即回傳True：
def isSubTree(self, root, subRoot):
def dfs(root, subRoot):
# some function that returns True when certain conditions are met
if not root: return
if self.isSubtree(root.left, subRoot):
return True
if self.isSubtree(root.right, subRoot):
return True
if root.val == subRoot.val:
if dfs(root, subRoot):
return True
return False
如果它們的任何子節點找到了解決方案，則您需要遞回樹中的中間節點來向上傳輸資訊。否則，您會丟棄在遞回樹的更深層次之一中找到解決方案的資訊，并且您只能獲得根的結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383321.html