本文主要是介绍Day59 代码随想录打卡|二叉树篇---把二叉搜索树转换为累加树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目（leecode T538）：
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
方法：本题的题目乍一看有些难理解，要把大于等于当前节点的值的总和全部相加作为该节点的新值。因为该树是二叉搜索树，所以其实他的中序遍历是递增有序的，所以其实我们可以获得该二叉搜索树的中序遍历结果，在这个数组上从后到前进行累加即可。因为中序遍历的顺序是左中右，如果想要更方便一些我们可以使用反中序遍历，即右中左的顺序。了解了这些我们如何具体操作呢，其实我们用到的是之前用过的思路，即使用一个pre节点来保存当前遍历节点的前一个节点，这样我们就方便累加了。递归三要素分析：
1：传入参数与返回值：传入树节点指针即可，因为我们要对整个树进行遍历操作，所以不需要返回值。
2：终止条件：当遇到空即可返回
3：单层处理逻辑：我们对树进行反中序遍历操作，把每一个节点的值都修改为当前节点的值加上上一个节点的值，具体就是用一个pre来保存上一个节点的值。但注意一定要用反中序遍历的顺序。
题解：
class Solution {
private:int pre = 0;void traversal(TreeNode* node){if(node == NULL) return; //终止条件traversal(node->right); //右node->val += pre; //中pre = node->val;traversal(node->left); //左}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};这篇关于Day59 代码随想录打卡|二叉树篇---把二叉搜索树转换为累加树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
