iT邦幫忙

1

Leetcode 1660. Correct a Binary Tree 的問題

各位高人好,本人在刷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。請問是為什麼呢? 先謝謝各位願意看完我的問題,有不清楚的地方我會再補充!

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 個回答

0
海綿寶寶
iT邦大神 1 級 ‧ 2021-08-12 09:12:55
最佳解答

這程式跟你寫的很像
你可以研究看看差別在那裡

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
ffaanngg iT邦新手 5 級 ‧ 2021-08-12 11:32:52 檢舉

感謝! 其實這個方法我也看過,就是記錄父節點。我的問題就是在於...一定要記錄父節點嗎? 像我一樣找到invalid node之後直接設為None,為什麼不可行?

0
一級屠豬士
iT邦大師 1 級 ‧ 2021-08-12 08:22:21

除錯程式,基本的方式,就是列印一些變數的值出來觀察.
for _ in range(len(queue)):
curr = queue.popleft()

補充個 i 吧, for i in ...
然後把每一次 for loop 執行, i 還有其他變數的值列印出來觀察.
記得加上分隔線, 區分每次loop,比較好觀察.

另外許多問題,都要考慮一些邊界情況,希望你能藉此程式增加功力.加油!

我要發表回答

立即登入回答