企业官网建设流程全解析

题目

给出二叉搜索树的根节点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和10<sup>4</sup>^ ^之间。
• 每个节点的值介于-10<sup>4</sup>和10<sup>4</sup>之间。
• 树中的所有值互不相同。
• 给定的树为二叉搜索树。

算法

只需要反序 中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

正常的中序遍历实现如下

// 中序遍历：左 -> 根 -> 右publicvoidinorderRecursive(TreeNoderoot){if(root==null)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{intsum=0;publicTreeNodeconvertBST(TreeNoderoot){if(root!=null){convertBST(root.right);sum+=root.val;root.val=sum;convertBST(root.left);}returnroot;}}