LeetCode Solutions
538. Convert BST to Greater Tree
Time: $O(n)$ Space: $O(\log n)$
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int prefix = 0;
reversedInorder(root, prefix);
return root;
}
private:
void reversedInorder(TreeNode* root, int& prefix) {
if (root == nullptr)
return;
reversedInorder(root->right, prefix);
prefix += root->val;
root->val = prefix;
reversedInorder(root->left, prefix);
}
};
class Solution {
public TreeNode convertBST(TreeNode root) {
reversedInorder(root);
return root;
}
private int prefix = 0;
private void reversedInorder(TreeNode root) {
if (root == null)
return;
reversedInorder(root.right);
prefix += root.val;
root.val = prefix;
reversedInorder(root.left);
}
}
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
prefix = 0
def reversedInorder(root: Optional[TreeNode]) -> None:
nonlocal prefix
if not root:
return
reversedInorder(root.right)
prefix += root.val
root.val = prefix
reversedInorder(root.left)
reversedInorder(root)
return root