作者VivianAnn (薇薇安安)
看板Python
標題[問題] Leetcode 1660，tree的問題
時間Wed Aug 18 11:33:17 2021
各位版友好，在刷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。請問是為什
麼呢？ 我先謝謝各位願意看完我的問題，有不清楚的地方我會再補充!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.170.26.70 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1629257599.A.4EB.html
1F：→ aassdd926: 你的queue先塞的是3再來是2吧，所以找不到 08/18 11:44
2F：推 aassdd926: 喔我看錯了 先塞右子樹是對的 08/18 11:52
3F：推 aassdd926: 因為我不是用python刷，所以不太確定，但看起來有兩種 08/18 12:00
4F：→ aassdd926: 可能，一是set 沒找到，二是curr = None這行沒改到， 08/18 12:00
5F：→ aassdd926: 可以檢查看看 08/18 12:00
6F：→ VivianAnn: 我看Discuss裡的解法都是去紀錄每個節點的父節點 08/18 12:24
7F：→ VivianAnn: 找到invalid node後再由invalid node的父節點去改 08/18 12:24
8F：→ VivianAnn: 那個方法我懂，但我想知道這個方法為什麼行不通 08/18 12:25
9F：→ VivianAnn: curr = None 這行，我測試是有改到.... 08/18 12:26
10F：推 aassdd926: 我剛剛檢查了id ，發現curr=None 讓curr 這個變數refe 08/18 16:21
11F：→ aassdd926: r to None value, which is a new space 08/18 16:21
12F：→ VivianAnn: 不懂耶，把curr的ref設為null不是我們想要的嗎？ 08/18 21:40
13F：→ aassdd926: 是新設一個存 None的空間，然後curr 這個指針指過去， 08/18 23:22
14F：→ aassdd926: 所以原本的 node(2)還留著 08/18 23:22
15F：→ aassdd926: 所以你是改指針指去的位置，而不是指針原本指的空間的 08/18 23:27
16F：→ aassdd926: 值 08/18 23:27
17F：→ VivianAnn: 謝謝，我懂了，這樣的話只能由父節點去改了 08/19 23:40