LeetCode_78_ConvertBSTTOGreaterTree

1. question: 把二叉搜索树转换为累加树（中等）

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

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/convert-bst-to-greater-tree

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

2. answers

这道题初步看还是没什么思路的，但是仔细一看，可以发现，累加树就是将其大于等于当前节点的值累加。那么大于等于当前节点，其实就是中序遍历的当前节点的后面序列。也就是中序遍历逆序的前面序列。

因此可逆序中序遍历，记录累加值即可。代码如下所示：

public class Solution_0077 {

    // 递归逆中序遍历
    public int midOrder(TreeNode tn, int val) {

        // 注意，递归终止条件的返回值（因为如果当前是null，也就是当前val无需更新，即上一步传进来的值，也就是递增序列的下一个元素）
        if(tn == null) return val;

        // 递归右子树
        int newVal = midOrder(tn.right, val);

        // 修改当前值
        tn.val += newVal;

        // 递归左子树
        return midOrder(tn.left, tn.val);
    }

    public TreeNode convertBST(TreeNode root) {

        int result = midOrder(root, 0);
        return root;
    }

    public static void main(String[] args) {
        System.out.println();

//        TreeNode tn9 = new TreeNode(8);
//        TreeNode tn8 = new TreeNode(3);
//        TreeNode tn7 = new TreeNode(7, null, tn9);
//        TreeNode tn6 = new TreeNode(5);
//        TreeNode tn5 = new TreeNode(2, null, tn8);
//        TreeNode tn4 = new TreeNode(0);
//        TreeNode tn3 = new TreeNode(6, tn6, tn7);
//        TreeNode tn2 = new TreeNode(1, tn4, tn5);
//        TreeNode tn1 = new TreeNode(4, tn2, tn3);


        TreeNode tn2 = new TreeNode(1);
        TreeNode tn1 = new TreeNode(0, null, tn2);

        Solution_0077 s = new Solution_0077();

        s.convertBST(tn1);

        // 层序遍历
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(tn1);

        while(queue.size() > 0 ) {

            int length = queue.size();

            while(length-- > 0) {

                tn1 = queue.poll();

                System.out.print(tn1.val + "\t");

                if(tn1.left != null) queue.offer(tn1.left);
                if(tn1.right != null) queue.offer(tn1.right);

            }

            System.out.println();
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。