LeetCode.538.Convert BST to Greater Tree BST转换为累加树

题目描述

538 Convert BST to Greater Tree
https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

---

解题过程

这道题挺好的，不算太难，也有意思。
为了给每个结点的值做累加，需要知道所有大于他的结点和（在右子树中），所以需要中序遍历。
用递归来写，过程中返回当前子树的所有结点的原始值的和，便于累加，同时修改结点的值。
时间复杂度 O(n), 空间复杂度 O(n)
官方题解的递归方法中用一个全局变量保存比当前节点大的所有结点的和，使代码非常简便。

private static class SolutionV2020 {
    public TreeNode convertBST(TreeNode root) {
        postOrderTraverse(root, 0);
        return root;
    }

    // 递归后续遍历二叉树，greaterSum是父节点中比root值大的累加和，返回所有节点原始值的和
    private int postOrderTraverse(TreeNode root, int greaterSum) {
        if (null == root) {
            return 0;
        }
        // 叶节点
        if (null == root.left && null == root.right) {
            int res = root.val;
            root.val += greaterSum;
            return res;
        }
        // 右子树需累加： greaterSum
        int rightSum = postOrderTraverse(root.right, greaterSum);
        // 左子树需累加： 父节点 + 父节点右子树 + greaterSum
        int leftSum = postOrderTraverse(root.left, rightSum + root.val + greaterSum);
        // 子树root所有结点的原始值的和
        int sum = rightSum + leftSum + root.val;
        // 根节点需要累加： 右子树 + greaterSum
        root.val += rightSum + greaterSum;
        return sum;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_538_ConvertBSTToGreaterTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_538_ConvertBSTToGreaterTree.java

---