1 题目

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

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree）

累加树：每个节点 node 的新值等于 原树中大于或等于node.val的值之和。

就是将原节点的值小的节点的值变为后面大的累加的值

例子

ACM模式：这里采用完全二叉树的方式构建二叉树

2 思路

原来值小的节点的新值是原来值大的节点的累加，这里需要对节点进行排序了

但是二叉搜索树又是排序好的，即中序遍历后的值就是排序好的值，左中右二叉搜索树为升序

这里的需求又是从大的值向小的值累加，可以将中序遍历的左右顺序颠倒，即左中右是升序排序，右中左是降序排序；可以采用右中左的顺序进行排序，在递归遍历的时候加入prev指针保存累加的值

java">class Solution{public TreeNode convertBST(TreeNode root) {inorderReverseTree(root);return root;}private TreeNode prev = null;private void inorderReverseTree(TreeNode root) {if (root != null) {inorderReverseTree(root.right);if (prev != null) {root.val = root.val + prev.val;}prev = root;inorderReverseTree(root.left);}}
}

Note： prev指针的使用方式，先判空，非空时已经保存了之前的值，然后再赋值

3 ACM模式

java">import java.util.*;class TreeNode{int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val; }}// Solutionpublic class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);Solution solution = new Solution();String[] nums = in.nextLine().split(" ");List<TreeNode> nodes = new ArrayList<>();for (String num: nums) {if (!num.isEmpty()) {if ("null".equals(num)) {nodes.add(null);} else {nodes.add(new TreeNode(Integer.parseInt(num)));}}}constructTree(nodes);TreeNode root = nodes.get(0);solution.convertBST(root);preorderTree(root);}// 使用满二叉树public static void constructTree(List<TreeNode> nodes) {for (int i = 0; 2*i+1 < nodes.size(); i++) {if (nodes.get(i) != null) {nodes.get(i).left = nodes.get(2*i+1);if (2*i+2 < nodes.size()) {nodes.get(i).right = nodes.get(2*i+2);}}}}public static void preorderTree(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preorderTree(root.left);preorderTree(root.right);}}
}
/*
test case:
4 1 6 0 2 5 7 null null null 3 null null null 8*/

---

参考

https://programmercarl.com/0538.把二叉搜索树转换为累加树.html