Java 求解如何把二叉搜索树转换为累加树

一、题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

二、题解

观察示例图发现，树的遍历顺序为右，中，左的顺序，每个节点的值，是按照这个顺序累加的状态

由于是需要累加，所以需要pre指针记录当前遍历节点cur的前一个节点，方便累加

（1）确定递归函数及返回值

题目需要遍历整棵树，同时需要定义一个全局变量 pre，用来保存 cur节点的前一个节点的数值

（2）确定递归终止条件

遇到空就终止

（3）确定单层递归的逻辑

遍历的顺序，右，中，左

三、代码

class Solution {
    // 记录前驱节点
    int pre = 0;

    public TreeNode convertBST(TreeNode root) {
        // 空节点终止
        if (root == null) {
            return root;
        }
        // 遍历顺序：右，中，左
        convertBST(root.right);
        root.val += pre;
        pre = root.val;
        convertBST(root.left);
        return root;
    }
}

四、总结

观察示例节点的规律，需要记录上个节点的情况，注意引入前驱节点pre