1038. Binary Search Tree to Greater Sum Tree

Description

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

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Solution

根据二叉搜索树的特点，一个节点的右孩子的值均大于该节点，若该节点不是根节点，且它是它的父节点的左孩子，则父节点的值也大于该节点的值。使用后序遍历，依次将累加和加到当前节点即可。

Code

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        stack<TreeNode*> nodes;
        TreeNode* head = root;
        int sum = 0;
        while (!nodes.empty() || root) {
            while (root) {
                nodes.push(root);
                root = root->right;
            }
            root = nodes.top();
            nodes.pop();
            root->val += sum;
            sum = root->val;
            root = root->left;
        }
        return head;
    }
};