制作介绍的网站模板免费下载,好123设为主页官网,东莞推广系统电话,儿童网站设计模板给出二叉 搜索 树的根节点#xff0c;该树的节点值各不相同#xff0c;请你将其转换为累加树#xff08;Greater Sum Tree#xff09;#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下#xff0c;二叉搜索树满足下列约束条件#…给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下二叉搜索树满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
注意本题和 1038: . - 力扣LeetCode 相同 示例 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 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。
思路
一看到累加树相信很多小伙伴都会疑惑如何累加遇到一个节点然后再遍历其他节点累加怎么一想这么麻烦呢。
然后再发现这是一棵二叉搜索树二叉搜索树啊这是有序的啊。
那么有序的元素如何求累加呢
其实这就是一棵树大家可能看起来有点别扭换一个角度来看这就是一个有序数组[2, 5, 13]求从后到前的累加数组也就是[20, 18, 13]是不是感觉这就简单了。
为什么变成数组就是感觉简单了呢
因为数组大家都知道怎么遍历啊从后向前挨个累加就完事了这换成了二叉搜索树看起来就别扭了一些是不是。
那么知道如何遍历这个二叉树也就迎刃而解了从树中可以看出累加的顺序是右中左所以我们需要反中序遍历这个二叉树然后顺序累加就可以了。
#递归
遍历顺序如图所示 本题依然需要一个pre指针记录当前遍历节点cur的前一个节点这样才方便做累加。
pre指针的使用技巧我们在二叉树搜索树的最小绝对差 (opens new window)和二叉树我的众数是多少 (opens new window)都提到了这是常用的操作手段。
递归函数参数以及返回值
这里很明确了不需要递归函数的返回值做什么操作了要遍历整棵树。
同时需要定义一个全局变量pre用来保存cur节点的前一个节点的数值定义为int型就可以了。
代码如下
int pre 0; // 记录前一个节点的数值
void traversal(TreeNode* cur)确定终止条件
遇空就终止。
if (cur NULL) return;确定单层递归的逻辑
注意要右中左来遍历二叉树 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
代码如下
traversal(cur-right); // 右
cur-val pre; // 中
pre cur-val;
traversal(cur-left); // 左递归法整体代码如下
class Solution {
private:int pre 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur NULL) return;traversal(cur-right);cur-val pre;pre cur-val;traversal(cur-left);}
public:TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
};#迭代法
迭代法其实就是中序模板题了在二叉树前中后序迭代法 (opens new window)和二叉树前中后序统一方式迭代法 (opens new window)可以选一种自己习惯的写法。
这里我给出其中的一种代码如下
class Solution {
private:int pre; // 记录前一个节点的数值void traversal(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) {st.push(cur);cur cur-right; // 右} else {cur st.top(); // 中st.pop();cur-val pre;pre cur-val;cur cur-left; // 左}}}
public:TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
};#总结
经历了前面各种二叉树增删改查的洗礼之后这道题目应该比较简单了。
好了二叉树已经接近尾声了接下来就是要对二叉树来一个大总结了
