云空间可以做网站,网站建设0doit,亚马逊怎么做网站推广,下载app官方正版题目 给出二叉 搜索 树的根节点#xff0c;该树的节点值各不相同#xff0c;请你将其转换为累加树#xff08;Greater Sum Tree#xff09;#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下#xff0c;二叉搜索树满足下列约束条件该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 注意本题和 1038: https://leetcode-cn.com/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 和 104 之间。 每个节点的值介于 -104 和 104 之间。 树中的所有值 互不相同 。 给定的树为二叉搜索树。
解题思路 从示例中可知累加树是从最右下角出发逐渐相加变大由此想到右-中-左的顺序遍历二叉搜索树在单层逻辑里累加节点的值。定义pre为上一个节点的值。
代码实现
class Solution {
public:TreeNode* convertBST(TreeNode* root) {pre0;traserval(root);return root;}private:int pre0;void traserval(TreeNode* cur) {if (curnullptr) return;traserval(cur-right);cur-val pre;precur-val;traserval(cur-left);}
};
