当前位置: 首页> 汽车> 时评 > 189.二叉树:把二叉搜索树转换为累加树(力扣)

189.二叉树:把二叉搜索树转换为累加树(力扣)

时间:2025/7/11 22:42:16来源:https://blog.csdn.net/weixin_63779802/article/details/139856673 浏览次数: 0次

代码解决

/*** 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:// pre 用于保存累加和int pre = 0;// 中序遍历函数,按照右-根-左的顺序遍历void traversal(TreeNode* root){if (root == nullptr) return;// 遍历右子树traversal(root->right);// 更新节点值root->val += pre;// 更新累加和pre = root->val;// 遍历左子树traversal(root->left);}// 将BST转换成累加树的函数TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};

代码使用了递归的方法。主要思路是使用中序遍历的方式遍历二叉搜索树,但改变遍历的顺序,即先遍历右子树,然后访问当前节点,最后遍历左子树。在遍历过程中,每次访问一个节点时,将该节点的值加上其所有右子节点的值。

这里简要解释一下代码的工作流程:

  1. 定义一个全局变量 pre 用于记录累加和,初始值为0。
  2. 定义一个辅助函数 traversal,它接受当前节点作为参数。
  3. 如果当前节点为空,则返回。
  4. 首先遍历右子树。
  5. 更新当前节点的值为其自身值加上 pre
  6. 更新 pre 为当前节点的值。
  7. 然后遍历左子树。
  8. 在 convertBST 函数中,调用 traversal 函数开始中序遍历,并返回转换后的根节点。

这个算法的时间复杂度是 O(n),其中 n 是树中节点的数量。空间复杂度也是 O(n),因为需要存储递归调用的栈。

关键字:189.二叉树:把二叉搜索树转换为累加树(力扣)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: