力扣-538-把二叉搜索树转换为累加树

题目：
538. Convert BST to Greater Tree(easy)

题目大意：
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

1 2 3 4 5 6 7 8 9 10

例如： 输入: 原始二叉搜索树: 5 / \ 2 13 输出: 转换为累加树: 18 / \ 20 13

解题思路：
首先要搞懂累加树的定义：树中所有结点的值更新为所有比其大的结点之和。
其次，本题是在二叉排序树(又称二叉搜索树、二叉查找树)上进行操作，其性质：左子树不空则左子树上所有结点值均小于其根结点，右子树不空则右子树上所有结点值均大于其根结点，整个树还是个递归的结构。所以该树最明显特征就是中序遍历可以得到一个递增的序列。
根据以上两点特征，可以推出本题的入手点：
右子树的最右孩子结点一定是最大结点，左子树的最左孩子一定是最小结点，所以类比中序遍历，但是先遍历右子树，再处理根节点，最后处理左子树的顺序。代码也很好理解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Java:
public TreeNode convertBST(TreeNode root){
    if(root == null) return null;
    int[] sum = new int[1];
    return convertBST(root,sum);  
}

private TreeNode convertBST(TreeNode root,int[] sum){
    if(root == null) return null;
    convertBST(root.right,sum);
    sum[0] += root.val;
    root.val = sum[0];
    convertBST(root.left,sum);

    return root;
}