- 把二叉搜索树转换为累加树
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:
5/ \2 13输出: 转换为累加树:18/ \20 13
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
1.利用各种集合来做，就是任意一种遍历方式，获取所有的数据集合，然后先排序，再遍历一次修改数据
class Solution {ArrayList<Integer> list;HashMap<Integer, Integer> map;public TreeNode convertBST(TreeNode root) {if(root == null) return null;list = new ArrayList<>();dfs(root);Collections.sort(list);//排序map = new HashMap<>();//将应该修改的值放在map中int sum = 0;for(Integer nn:list){sum += nn;}int tmp = 0;for(Integer nn: list){map.put(nn, sum - tmp);tmp += nn;}dfs2(root);//更新return root;}void dfs(TreeNode root){if(root == null) return;list.add(root.val);dfs(root.left);dfs(root.right);}void dfs2(TreeNode root){if(root == null) return;root.val = map.get(root.val);dfs2(root.left);dfs2(root.right);}
}
2.注意题意已经说明，这是一个二叉搜索树，上面的解法，并没有用到这个前提，
这里直接利用变形的中序遍历，这样求和的时候直接可操作
class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;else{//变形的中序遍历，先右边，再左边convertBST(root.right);sum += root.val;//就是这两行root.val = sum;convertBST(root.left);}return root;}
}
可以直接这样写的
class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;convertBST(root.right);sum += root.val;root.val = sum;convertBST(root.left);return root;}}
不太习惯直接在原函数递推，特别还是返回值
class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;//一般我会再创建一个函数dfs(root);return root;}void dfs(TreeNode root){//这里有返回值一样也是可以的if(root == null) return;dfs(root.right);sum += root.val;root.val = sum;dfs(root.left);}
}
3.利用迭代的方法来求，其实就是变形的中序遍历迭代方法，右中左，利用一个栈
class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {if(root == null) return null;//迭代方法TreeNode node = root;//先提前保存LinkedList<TreeNode> st = new LinkedList<>();while(root != null || !st.isEmpty()){while(root!= null){st.push(root);root = root.right;}root = st.pop();sum += root.val;//注意这个是在前面，因为是包含本身的值root.val = sum;root = root.left;}//return root;注意因为这个又返回值，但是root一直在变化return node;}
}
众所周知，二叉树的先序遍历一共两种方式，这里只适用于上面那种，对于另一种则不适用，因为那个只能从根节点开始相加
