[数据结构与算法]【LeetCode】每日一题2021/10/19

• 思路
  想到一种思路，先全部遍历一遍，求和，然后再按照中序遍历来遍历一遍，同时遍历的时候减去当前值就是下一个节点的值。
  参考题解：换一种思路，从后往前累加，之前的是累减，还需要求和，现在换成累加，然后从后往前，把中序遍历反过来，右中左。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum;
    public void inBST(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // 右
        inBST(root.right);
        // 中
        sum += root.val;
        root.val = sum;
        // 左
        inBST(root.left);
    }
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        inBST(root);
        return root;
    }
}