网站会员管理,宝塔管理wordpress,怎么获得免费网站,做soho要不要注册网站力扣日记#xff1a;【二叉树篇】538. 把二叉搜索树转换为累加树 日期#xff1a;2023.1.19 参考#xff1a;代码随想录、力扣 ps#xff1a;因为准备组会汇报又搁置了好久#xff08;其实就是懒逃避T^T)#xff0c;但这是最后一道二叉树啦啊啊啊#xff01;#xff01…力扣日记【二叉树篇】538. 把二叉搜索树转换为累加树 日期2023.1.19 参考代码随想录、力扣 ps因为准备组会汇报又搁置了好久其实就是懒逃避T^T)但这是最后一道二叉树啦啊啊啊 538. 把二叉搜索树转换为累加树
题目描述 难度 给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下二叉搜索树满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。 注意本题和 第1038题 相同
示例 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^4 之间。每个节点的值介于 -10^4 和 10^4 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。
题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* convertBST(TreeNode* root) {traversal(root); // 遍历完后每个节点的新值都更新了return root;}// 思路按照 右中左 的顺序遍历节点的值加上当前累积值即为新的节点值// 并将当前累加值更新为新节点值相当于累积值边遍历边累加int val 0; // 记录当前累加值(全局变量每遍历一个值会加上现在遍历到的值)void traversal(TreeNode* root) {// 右中左(逆序)if (root nullptr) return;// 右traversal(root-right); // 向右递归遍历// 中root-val val; // 当前值加上累积值val root-val; // 更新累积值(相当于原累积值加上了当前值)// 左traversal(root-left); // 向左递归遍历}};复杂度
时间复杂度 空间复杂度
思路总结
思路按照 右中左 的顺序遍历节点的值加上当前累积值即为新的节点值同时将当前累加值更新为新节点值相当于累积值边遍历边累加这个思路是我瞅着示例图模拟老半天才得出的结论悲对此代码随想录提供了一个很好的思路——“二叉搜索树root [5,2,13]换一个角度来看就是一个有序数组[2, 5, 13]求从后到前的累加数组也就是[20, 18, 13]是不是感觉这就简单了 ”也就是说对该二叉搜索树进行逆向中序遍历右左中先遍历到13(13013)再遍历到551318为新值再遍历到221820为新值。对示例图中的二叉树也是一样通过一个值来累积遍历到的节点值每遍历到一个节点就加上这个累积值实际上也是上一个遍历到的节点的新值作为新节点值即可。所以通过一个递归函数右中左来进行逆向中序遍历并用一个全局变量来记录累积值不要用传递参数或者返回值来记录累积值会相当麻烦直接用全局变量即可其实就是一个指向上一个节点的指针
