LeetCode刷题实战538：把二叉搜索树转换为累加树-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 把二叉搜索树转换为累加树，我们先来看题面：

https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

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.

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例

解题

思路：多写两层搜索树就会很明显的发现，所求的每个节点的值就是该节点的右子树所有节点的和加上自身的节点值，所以采用中序遍历，从右子树开始遍历即可，设置一个全局变量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;
    }
}