累加树

/** * 给定一个二叉搜索树（Binary Search Tree）， * 把它转换成为累加树（Greater Tree)， * 使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 */
public  class GreaterTree{
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    /** * 思路： * 二叉搜索树中序遍历是递增的序列，那么反中序（右中左）的顺序就是降序序列 * 那么只需要把前面的数依次加到节点处就是当前累加树节点的和 * @param root * @return */
    public TreeNode convertBST(TreeNode root) {
          int sum = 0;
          if (root == null) return null;
          convertBST(root.right);
          sum += root.val;
          root.val = sum;
          convertBST(root.left);
          return root;
    }
}