[問題] Leetcode 1660,tree的問題

作者: VivianAnn (薇薇安安)   2021-08-18 11:33:17
各位版友好,在刷leetcode 1660時碰到了一個問題,但不知錯誤在哪。
我的想法是使用BFS,逐個level找題目所要的invalid node,找到的話就將invalid node
的本身,以及其左右子樹設為None。
以下是我的code:
# 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。請問是為什
麼呢? 我先謝謝各位願意看完我的問題,有不清楚的地方我會再補充!
作者: aassdd926 (打東東)   2021-08-18 11:44:00
你的queue先塞的是3再來是2吧,所以找不到喔我看錯了 先塞右子樹是對的因為我不是用python刷,所以不太確定,但看起來有兩種可能,一是set 沒找到,二是curr = None這行沒改到,可以檢查看看
作者: VivianAnn (薇薇安安)   2021-08-18 12:24:00
我看Discuss裡的解法都是去紀錄每個節點的父節點找到invalid node後再由invalid node的父節點去改那個方法我懂,但我想知道這個方法為什麼行不通curr = None 這行,我測試是有改到....
作者: aassdd926 (打東東)   2021-08-18 16:21:00
我剛剛檢查了id ,發現curr=None 讓curr 這個變數refer to None value, which is a new space
作者: VivianAnn (薇薇安安)   2021-08-18 21:40:00
不懂耶,把curr的ref設為null不是我們想要的嗎?
作者: aassdd926 (打東東)   2021-08-18 23:22:00
是新設一個存 None的空間,然後curr 這個指針指過去,所以原本的 node(2)還留著所以你是改指針指去的位置,而不是指針原本指的空間的值
作者: VivianAnn (薇薇安安)   2021-08-19 23:40:00
謝謝,我懂了,這樣的話只能由父節點去改了

Links booklink

Contact Us: admin [ a t ] ucptt.com