题目介绍（leetcode 1038）
- 中文描述（具体题意看思路分析）
给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键小于节点键的节点。
- 节点的右子树仅包含键大于节点键的节点。
- 左右子树也必须是二叉搜索树。
思路
tree.png
- 题意每个节点重新赋值，值为>= 本节点值得所有节点的和（对搜索二叉树来书就是当前节点所有右边的节点）
解决方案
暴力法
- 1、遍历所有节点保存，然后继续遍历 计算每个节点的值
改进法
- 1、我们知道先序遍历中 某个节点的左边（右边）在二叉树中均在此节点左边（右边）
- 2、搜索二叉树是从左往右依次扩大的
- 3、所以我们参照先序遍历方法，采用「right - root -left 」的顺序遍历然后直接遍历list 相加即可。
具体实现
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public static TreeNode bstToGst(TreeNode root) {
inOrder(root);
int sum = 0;
for (TreeNode node : list) {
sum += node.val;
node.val = sum;
}
return root;
}
static ArrayList<TreeNode> list = new ArrayList<>();
private static void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.right);
list.add(root);
inOrder(root.left);
}
