# 538     Convert BST to Greater Tree

## 538. [Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/description/)

## 1. Question

Given 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 sum of all keys greater than the original key in BST.

**Example:**

```
Input:
 The root of a Binary Search Tree like this:
              5
            /   \
           2     13


Output:
 The root of a Greater Tree like this:
             18
            /   \
          20     13
```

## 2. Implementation

**(1) DFS**

思路: 规律比较明显，对于每个node，先处理右子树，累加右子树的和，然后更新当前node的值，再处理左子树

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        int[] sum = new int[1];
        convertBST(root, sum);
        return root;
    }

    public void convertBST(TreeNode node, int[] sum) {
        if (node == null) {
            return;
        }

        convertBST(node.right, sum);
        node.val += sum[0];
        sum[0] = node.val;
        convertBST(node.left, sum);
    }
}
```

## 3. Time & Space Complexity

DFS: 时间复杂度O(n), 空间复杂度: O(h)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/tree/538-convert-bst-to-greater-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.