Java 求解如何把二叉搜索树转换为累加树
短信预约 -IT技能 免费直播动态提醒
一、题目
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
二、题解
观察示例图发现，树的遍历顺序为右，中，左的顺序，每个节点的值，是按照这个顺序累加的状态
由于是需要累加，所以需要pre指针记录当前遍历节点cur的前一个节点，方便累加
（1）确定递归函数及返回值
题目需要遍历整棵树，同时需要定义一个全局变量 pre，用来保存 cur节点的前一个节点的数值
（2）确定递归终止条件
遇到空就终止
（3）确定单层递归的逻辑
遍历的顺序，右，中，左
三、代码
class Solution {
// 记录前驱节点
int pre = 0;
public TreeNode convertBST(TreeNode root) {
// 空节点终止
if (root == null) {
return root;
}
// 遍历顺序：右，中，左
convertBST(root.right);
root.val += pre;
pre = root.val;
convertBST(root.left);
return root;
}
}
四、总结
观察示例节点的规律，需要记录上个节点的情况，注意引入前驱节点pre
到此这篇关于Java 求解如何把二叉搜索树转换为累加树的文章就介绍到这了,更多相关Java 二叉搜索树转换为累加树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
