题目描述

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

解法一

思路

还记得二叉搜索树的中序遍历结果是元素值由小到大有序的吗？这题要求把每个结点的值更新为比其大的结点值之和，那倒着来一遍中序遍历就好了。也就是说，由大到小遍历结点，每次累加比当前结点值大的和，赋值给当前结点就好了。为了让这个累加过程更容易实现，我们使用非递归版的中序遍历，而要让中序遍历反过来，就只需要先访问右子结点再访问左子结点（原本是先访问左子结点再访问右子结点）。

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        origin_root = root
        stack = []
        current = 0
        while root or stack:
            if root:
                stack.append(root)
                root = root.right
            else:
                node = stack.pop()
                current += node.val
                node.val = current
                root = node.left
        return origin_root

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode convertBST(TreeNode root) {
        TreeNode originRoot = root;
        Stack<TreeNode> stack = new Stack<>();
        int current = 0;
        while (root != null || !stack.empty()) {
            if (root != null) {
                stack.push(root);
                root = root.right;
            } else {
                TreeNode node = stack.pop();
                current += node.val;
                node.val = current;
                root = node.left;
            }
        }
        return originRoot;
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *convertBST(TreeNode *root) {
        TreeNode *originRoot = root;
        stack<TreeNode *> sta;
        int current = 0;
        while (root != nullptr || !sta.empty()) {
            if (root != nullptr) {
                sta.push(root);
                root = root->right;
            } else {
                TreeNode *node = sta.top();
                sta.pop();
                current += node->val;
                node->val = current;
                root = node->left;
            }
        }
        return originRoot;
    }
};