我正在解決 LeetCode 問題101。對稱樹：
給定
root二叉樹，檢查它是否是自身的鏡像（即，圍繞其中心對稱）。
這是我的代碼：
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
org_root_list=[]
def dfs(root: Optional[TreeNode]) -> None:
if not root:
return
dfs(root.left)
org_root_list.append(root.val)
dfs(root.right)
dfs(root)
def invert(root: Optional[TreeNode]) -> None:
if not root:
return
left, right = invert(root.left), invert(root.right) # dfs
root.left, root.right = root.right, root.left
invert(root)
root_list=[]
def dfs1(root: Optional[TreeNode]) -> None:
if not root:
return
dfs1(root.left)
root_list.append(root.val)
dfs1(root.right)
dfs1(root)
return root_list==org_root_list
我已經用這段代碼通過了 195/198 個測驗用例。它失敗的第一個測驗用例是：
[1,2,2,2,null,2]
Output: True
Expected: False
該invert函式的代碼反轉了樹。該dfs函式對原始根樹進行中序遍歷。然后dfs1對倒排樹進行中序遍歷，它們分別附加到兩個串列中。然后我們通過比較兩個串列是否相同來回傳結果。
uj5u.com熱心網友回復：
如果兩棵樹具有相同的有序序列，則它們是相同的，這是不正確的。例如，這些樹都具有相同的有序序列，因此dfs在它們上運行的結果將導致相同的輸出：
2 3 1
/ \ / \
1 3 2 2
/ \
1 3
解決此問題的一種方法是在遇到 時也產生一個值None，并使深度優先順序為預順序而不是順序。
關于您的代碼的其他一些說明：
left并且right不在invert函式中使用。如果事實上，它們總是None，因為invert總是回傳None。很遺憾你有兩個 dfs 函式，只是因為你需要不同串列中的輸出。將該函式轉換為生成器，以便呼叫者可以在他們想要的地方收集這些值。
這導致了這段代碼：
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(root: Optional[TreeNode]):
if not root:
yield None # extra value for each encountered None
return
yield root.val # pre-order instead of in-order
yield from dfs(root.left)
yield from dfs(root.right)
def invert(root: Optional[TreeNode]) -> None:
if not root:
return
invert(root.left)
invert(root.right)
root.left, root.right = root.right, root.left
org_root_list = list(dfs(root))
invert(root)
return list(dfs(root)) == org_root_list
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489061.html
上一篇：將串列物件轉換為另一個結構