各位高人好,本人在刷leetcode 1660,以下是本人的Python程式碼,但不知為何會有錯。
我的想法是使用BFS,逐個level找題目所要的invalid node。找到的話就將invalid node的本身,以及其左右子樹設為None。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def correctBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
queue = collections.deque([root])
while queue:
visited = set()
for _ in range(len(queue)):
curr = queue.popleft()
visited.add(curr)
if curr.right in visited:
curr.left = None
curr.right = None
curr = None
continue
if curr.right:
queue.append(curr.right)
if curr.left:
queue.append(curr.left)
return root
但是,對於這個test case
[1,2,3]
2
3
我所return的還是原本的樹:[1,2,3],顯然invalid node沒有被設為None。請問是為什麼呢? 先謝謝各位願意看完我的問題,有不清楚的地方我會再補充!
這程式跟你寫的很像
你可以研究看看差別在那裡
class Solution:
def correctBinaryTree(self, root: TreeNode) -> TreeNode:
visited = {root}
queue = collections.deque([(root, None)])
while queue:
node, father = queue.popleft()
if node.right in visited:
if father.left == node:
father.left = None
else:
father.right = None
return root
if node.right:
queue.append((node.right, node))
if node.left:
queue.append((node.left, node))
visited.add(node)
return root
除錯程式,基本的方式,就是列印一些變數的值出來觀察.
for _ in range(len(queue)):
curr = queue.popleft()
補充個 i 吧, for i in ...
然後把每一次 for loop 執行, i 還有其他變數的值列印出來觀察.
記得加上分隔線, 區分每次loop,比較好觀察.
另外許多問題,都要考慮一些邊界情況,希望你能藉此程式增加功力.加油!