从二叉树中删除节点

Question

我目前正在研究 leetcode 问题 366，我们必须找到包含每一代叶子值的列表列表。我想通过递归来实现这一点，如果一个节点没有左或右子节点，则记录该值，然后通过将其设置为 None 来删除该节点。这是我的代码：

def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
    leaf_list = []
    sub_list = []
    def traverse(node):
        if node == None:
            return
        if node.left == None and node.right == None:
            sub_list.append(node.val)
            node = None
            return 
        traverse(node.left)
        traverse(node.right)
        return root
    
    while True:
        if root == None:
            break
        sub_list = []
        traverse(root)
        leaf_list.append(sub_list)
        print(leaf_list)
    return leaf_list

问题似乎是当某个节点设置为 None 时，不会保留该更改。为什么我无法将节点设置为 None 以将其删除？

谢谢

Answer 1

只有当您分配给一个节点的属性时，树才能发生变异。对变量的赋值只会改变变量所代表的内容。这样的分配 never 会影响该变量具有的任何 previous 值。分配给变量就像从一个值切换到另一个值而不影响任何数据结构。因此，您需要调整代码，以便将 None 分配给 left 或 right 属性。

例外是根节点本身。当根是叶子时，就没有父节点可以变异。然后，您只需丢弃树并切换到空树 (None)。

实现此目的的一种方法是使用 traverse 的 return 值来更新 child-reference (left 或 right) traverse 的调用者需要更新。

这是您进行了这些改编的代码：

def findLeaves(root):
    sub_list = []
    def traverse(node):
        if not node:
            return
        if not node.left and not node.right:
            sub_list.append(node.val)
            return  # By returning None, the parent can remove it
        node.left = traverse(node.left)  # Assign the returned node reference
        node.right = traverse(node.right)
        return node  # Return the node (parent does not need to remove it)
    
    leaf_list = []
    while root:
        sub_list = []
        root = traverse(root)
        leaf_list.append(sub_list)
    return leaf_list

从二叉树中删除节点

Removing a node from binary tree

python

binary-tree