四川法制建设网站,app网站建设制作,多种网站,wordpress 下载短代码538. 把二叉搜索树转换为累加树
链接 给出二叉 搜索 树的根节点#xff0c;该树的节点值各不相同#xff0c;请你将其转换为累加树#xff08;Greater Sum Tree#xff09;#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下#xf…538. 把二叉搜索树转换为累加树
链接 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树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 之间。 树中的所有值 互不相同 。 给定的树为二叉搜索树。
思路 看图他是中序的倒叙进行变化的——右中左 后一个值前一个值后一个值 右8——中8715——左无 右15——中15621——左21526
返回值参数 返回值无 参数节点
void tra(TreeNode* root){终止条件 遍历完成节点为空 if(rootNULL) return ;单次递归 递归右子树 当前节点的值前一个节点值 存当前节点的值 递归左节点 tra(root-right);root-valpre;preroot-val;tra(root-left);代码
class Solution {
public:int pre0;void tra(TreeNode* root){if(rootNULL) return ;tra(root-right);root-valpre;preroot-val;tra(root-left);return ;}TreeNode* convertBST(TreeNode* root) {tra(root);return root;}
};
