BinarySearchTreeToGreatSumTree（

题目介绍（leetcode 1038）

• 中文描述（具体题意看思路分析）
  给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

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

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

思路

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);
    }