LC538 - 将二叉搜索树转换为累积树-2 个想法

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

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

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

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指针的使用方式，先判空，非空时已经保存了之前的值，然后再赋值