福州网站备案,济南网站建设公司电子商务网站,企业品牌推广策划方案,河北建筑工程信息网站题目
538. 把二叉搜索树转换为累加树
中等
相关标签
树 深度优先搜索 二叉搜索树 二叉树
给出二叉 搜索 树的根节点#xff0c;该树的节点值各不相同#xff0c;请你将其转换为累加树#xff08;Greater Sum Tree#xff09;#xff0c;使每个节点 node 的新值…题目
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 和 104 之间。每个节点的值介于 -104 和 104 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。
思路和解题方法 首先我们定义一个pre变量并将其初始化为0用于保存前缀和。然后我们定义一个traversal函数来遍历树。如果当前节点为空则返回。否则我们按照右子树、当前节点、左子树的顺序递归调用traversal函数。在遍历右子树之后我们将当前节点的值与pre相加并将结果赋给当前节点的值。这样做后当前节点的值就变成了大于等于它的所有节点值之和。接下来我们更新pre的值为当前节点的值以便在遍历左子树时使用。最后我们递归调用traversal函数来遍历左子树。在convertBST函数中我们调用traversal函数对树进行反向中序遍历并将修改后的根节点返回。 复杂度 时间复杂度: O(n) 时间复杂度O(n)其中 n 是二叉搜索树中的节点数量。因为我们需要遍历每个节点一次所以时间复杂度是线性的。 空间复杂度 O(h) 空间复杂度O(h)其中 h 是二叉搜索树的高度。在最坏情况下如果树是完全不平衡的即退化为链表递归调用栈的深度将是 O(n)。但在平衡的情况下二叉搜索树的高度是 O(logn)所以递归调用栈的深度是 O(logn)空间复杂度较低。 c 代码
class Solution {
public:int pre 0; // 前缀和初始化为0// 反向中序遍历将树上结点的值修改为大于等于它的所有值之和void traversal(TreeNode *root){if (root NULL) return; // 遍历到叶子结点时返回traversal(root-right); // 遍历右子树root-val pre; // 将当前结点的值加上前缀和pre root-val; // 更新前缀和traversal(root-left); // 遍历左子树}TreeNode* convertBST(TreeNode* root) {traversal(root); // 调用反向中序遍历函数return root; // 返回修改后的根节点}
};c迭代版本代码
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; // 初始化前缀和为0traversal(root); // 对二叉搜索树进行反向中序遍历return root; // 返回根节点}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
