题目描述

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.

样例

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

思路

题目意思是，每个节点的值都要转换为原来的节点值加上所有大于它的节点值之和。

因此我们可以降序遍历所有节点，并记录已经遍历过的节点值，累加到当前节点上。这样可以只遍历一次，以O(n)的复杂度完成题目要求。

利用BST树的性质，以右子、根、左子的顺序访问节点就可以由大到小遍历树。

方法1 递归

遍历树最直觉的方法是递归。

复杂度分析

时间复杂度 $O(n)$ 空间复杂度 $O(n)$

该算法在每个节点只执行一次，因此是线性时间的。
由于最坏的情况下树可能只有左子树或只有右子树，调用堆栈将包括n个节点。

C++ 代码

class Solution {
public:
    int sum=0;
    TreeNode* convertBST(TreeNode* root) {
        if(root==NULL)
           return NULL;

        convertBST(root->right);

        root->val+=sum; 
        sum=root->val;

        convertBST(root->left);   

        return root;
    }
};

方法2 用栈遍历树

以栈的方式遍历树，对每个节点，先压入其右子树，然后依次从栈中取出节点，访问该节点后访问其左子树。

复杂度分析

时间复杂度 $O(n)$ 空间复杂度 $O(n)$

C++ 代码

class Solution {
public:
     TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        stack<TreeNode*> st;
        TreeNode* node=root;
        while (!st.empty() || node != NULL) {

            while (node != NULL) {
                st.push(node);
                node = node->right;
            }

            node = st.top();
            st.pop();
            sum += node->val;
            node->val = sum;

            node = node->left;
        }

        return root;
    }
};