​LeetCode刷题实战538：把二叉搜索树转换为累加树

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 the 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:

1.The left subtree of a node contains only nodes with keys less than the node's key.

2.The right subtree of a node contains only nodes with keys greater than the node's key.

3.Both the left and right subtrees must also be binary search trees.

• 节点的左子树仅包含键 小于 节点键的节点。

• 节点的右子树仅包含键 大于 节点键的节点。

• 左右子树也必须是二叉搜索树。

示例                         

解题

思路：多写两层搜索树就会很明显的发现，所求的每个节点的值就是该节点的右子树所有节点的和加上自身的节点值，所以采用中序遍历，从右子树开始遍历即可，设置一个全局变量sum用于记录节点值的和。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */

class Solution {
 
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
 
        }
        return root;
    }
}