NeetCode #466LC-538MediumTrees
← Back to All Problems#466 · #538 · Convert BST to Greater Tree(把二叉搜索树转换为累加树)
📌 Problem Statement & Constraints
Given the root of a binary search tree, convert it to a greater sum tree: every node's new value is the sum of all values greater than or equal to the original value. Return the root. Constraints: the number of nodes is in
[0, 10^4], -10^4 <= Node.val <= 10^4.💡 Core Algorithmic Approaches
- Visit the nodes in descending order, which for a BST means a right-root-left traversal.
- Maintain a running total; at each node add its original value to the total and assign the total to the node.
- Because the traversal is descending, the running total at a node is exactly the sum of all values greater than or equal to it.
- This is the reverse of an in-order traversal and is O(n).
💻 Benchmark Python3 Implementation
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.total = 0
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
dfs(node.right) # largest values first
self.total += node.val # accumulate
node.val = self.total # this node sees all values >= its own
dfs(node.left)
dfs(root)
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one traversal.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Using a normal in-order traversal: it visits ascending, so the running total would be the sum of smaller values.
- Reading
node.valafter assigning it: the original value must be added to the total before the assignment. - Resetting the total between subtrees: it must accumulate across the whole traversal.
- Assuming values are non-negative: they can be negative, and the algorithm handles them.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.