如何在函数中转换树后 return 具有更新值的原始根节点

Question

我正在尝试 LeetCode 问题 538. Convert BST to Greater Tree:

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

Example 1

我解决这个问题的逻辑如下...

示例 BST 表示为顺序遍历：0 1 2 3 4 5 6 7 8

步骤 1

获取当前BST在列表中的顺序遍历-> [0, 1, 2, 3, 4, 5, 6, 7, 8]，其中每个元素代表一个节点

第 2 步

想法是将节点映射到它的更大总和
创建一个字典nodesToSums，它将一个节点映射到它的更大的总和
创建一个 sums 列表，其中每个元素代表每个节点的较大总和
上面的例子如下...
inOrderNodes = [0, 1, 2, 3, 4, 5, 6, 7, 8]、sums = [36, 36, 35, 33, 30, 26, 21, 15, 8] 以及将每个节点从 inOrderNodes 映射到其对应的更大总和的映射 sums。我们当然知道他们的立场。

这里我不确定是否可以通过遍历节点列表 inOrderNodes 或 nodesToSums 或原始 root 来做到这一点。在我的例子中，我决定我将在根上执行 BFS，并且对于每个节点，将当前节点值与其相应的更大总和交换 node.val = nodesToSums[node]
最后return root

我认为我的时间复杂度是 O(n)，但我不确定如何得出我的 space 复杂度。但我确实知道我正在为 inOrderNodes 列表使用 O(n)，为 nodesToSums 地图使用另一个 O(n)，为 queue 使用另一个 O(n)在我的 BFS 遍历中。我对每个说 O(n) 因为当 n 是 BST 中的节点数时它们都占用相同的 space。

好的，所以我认为我的逻辑是合理的，但我在最后 return root 打印了我的树的顺序遍历，然后我用它取回了原始根节点原始值。此外，它是我返回的唯一节点。糟糕，我做错了什么？在这一点上我有点迷路了。

这是我的代码...

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def convertBST(root):
    if root is None:
        return root

    nodes = inOrder(root)
    nodesToSums = calculateSums(nodes)

    queue = [root]

    while len(queue) > 0:
        node = queue.pop(0)
        node.val = nodesToSums[node]

        if node.left is not None:
            queue.append(node.left)

        if node.right is not None:
            queue.append(node.right)

    return root


def calculateSums(nodes):
    nodesToSums = {}
    sums = [node.value for node in nodes]

    for i in range(len(sums) - 1, -1, -1):
        if i == len(sums) - 1:
            nodesToSums[nodes[i]] = sums[i]
        else:
            sums[i] = sums[i] + sums[i + 1]
            nodesToSums[nodes[i]] = sums[i]

    return nodesToSums


def inOrder(root, nodes=[]):
    if root is None:
        return []

    inOrder(root.left, nodes)
    nodes.append(root)
    inOrder(root.right, nodes)

    return nodes


def printInOrder(root):
    if root is None:
        return

    inOrder(root.left)
    print(root.value, end="")
    inOrder(root.right)


root = BinaryTree(4)
root.left = BinaryTree(1)
root.right = BinaryTree(6)
root.left.left = BinaryTree(0)
root.left.right = BinaryTree(2)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(7)
root.left.right.right = BinaryTree(3)
root.right.right.right = BinaryTree(8)

convertBST(root)

printInOrder(root)

我不是在寻找解决方案，那里有很多人试图通过 post 灵活地制定他们自己的解决方案（我可以去 LeetCode 寻找这个或 google 答案） .但我正在寻找我提出的具体问题的答案 - 为什么只有根节点并且只有根节点在末尾 returned。拜托，任何其他post问题的解决方案不是对我的解决方案的更正对我没有帮助，我不想在练习时看到不同的解决方案。

Answer 1

以下是一些问题：

主要问题是您的代码同时使用 val 和 value 作为节点属性。在 LeetCode 问题中，class 定义了一个 val 属性，但是你的 class 有 value，其余的您的代码混合了 val 和 value 引用，因此 convertBST 不会更改现有属性，但会添加另一个属性。
printInOrder不应该调用inOrder，而是printInOrder。这个错误解释了为什么你的输出只有一个值。
printInOrder 将打印所有连接的内容。最好在 print 调用

end=" "

修复第一个要点后，您的代码将运行在 LeetCode 上正常运行，修复其他两个要点后，您也将在本地环境中获得预期的输出。

但是，我发现在这里使用字典有点矫枉过正。队列的使用也有点矫枉过正，因为此时访问节点的顺序不再重要；您可能只是遍历 nodes 列表。

in-order 遍历的想法很棒，但是如果您使用反向 in-order 遍历来遍历树会更实用。然后就可以累加运行宁和，在访问的同时更新节点，大大简化了代码。

这是一个剧透，以防其他访问者想知道它的外观（我使用 class 的 LeetCode 版本）：

class 树节点： def <strong>init</strong>(self, val=0, left=None, right=None): self.val = 值 self.left = 左 self.right = 对 def convertBST（根）：运行宁和= 0 对于 reversedInOrder(root) 中的节点：运行宁和+=node.val node.val = 运行宁和 return根 def reversedInOrder（根）：如果根：来自 reversedInOrder(root.right) 的收益屈服根来自 reversedInOrder(root.left)
的收益

如何在函数中转换树后 return 具有更新值的原始根节点

How to return original root node with updated values after converting tree in function

python

binary-search-tree

data-structures

Example 1

步骤 1

第 2 步