[问题] 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