(中序遍历）538. 把二叉搜索树转换为累加树

题目给出二叉搜索树的根节点root该树的节点值各不相同请你将其转换为累加树Greater Sum Tree将其转换为一个更大的树使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。注意本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-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和10sup4/sup^ ^之间。每个节点的值介于-10sup4/sup和10sup4/sup之间。树中的所有值互不相同。给定的树为二叉搜索树。算法只需要反序 中序遍历该二叉搜索树记录过程中的节点值之和并不断更新当前遍历到的节点的节点值即可得到题目要求的累加树。正常的中序遍历实现如下// 中序遍历左 - 根 - 右publicvoidinorderRecursive(TreeNoderoot){if(rootnull)return;inorderRecursive(root.left);// 递归左子树System.out.print(root.val );// 访问根节点inorderRecursive(root.right);// 递归右子树}现在遍历需要改为右 - 根 - 左详细代码如下代码/** * 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; * } * } */classSolution{intsum0;publicTreeNodeconvertBST(TreeNoderoot){if(root!null){convertBST(root.right);sumroot.val;root.valsum;convertBST(root.left);}returnroot;}}