当前位置：首页 > web >正文

【代码随想录day 20】力扣 538.把二叉搜索树转换为累加树

web 2025/8/15 7:52:44

视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP/?share_source=copy_web&vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
力扣题目：https://leetcode.cn/problems/convert-bst-to-greater-tree/

这道题可以使用双指针法，主要思路如下：

pre负责记录节点的值，初始值为0，cur负责遍历节点
因为是从大往小遍历，所以我们采用右中左的遍历方式
中间记录的时候cur的val与pre相加，并更新在当前节点上，pre更新到cur的值，cur再回溯到上一层
要注意，pre一定要跟上cur。

class Solution {
public:int pre=0;void traversal(TreeNode *cur){//终止条件if(cur == NULL) return ;//开始递归 从大到小遍历  右convertBST(cur->right);//中cur->val += pre;pre = cur->val;//左convertBST(cur->left);return;}TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};

迭代法也可以解决这道题，利用栈的先进后出特性，主要思路如下：
4. 首先从根节点往右子树走，一直到根节点，沿途的节点入栈。
5. 如果cur不为空或者栈不为空就持续循环，当节点不为空时，压入栈同时节点往右走；当节点为空时，取栈顶元素，与pre相加更新当前节点，再往左子树走，如果左子树存在就跳转到上一个判断条件压入栈

class Solution {
public://记录前一个节点的数值int pre = 0;void traversal(TreeNode *root){stack<TreeNode *> st;TreeNode *cur = root;//当cur不为空或栈不为空就执行循环while(cur != NULL || !st.empty()){   //如果cur不为空就入栈，可以用于判断是否有左子树if(cur !=NULL){st.push(cur);cur = cur->right;}else{//取栈顶元素cur=st.top();//弹出栈顶st.pop();//更新cur，pre跟上curcur->val += pre;pre=cur->val;//去找cur的左子树，如果有左子树，下次循环会存入栈中，如果没有，直接下一个栈顶元素cur=cur->left;}}}TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}

总体来说有点绕，可以参考下面这个流程：

# BST 转换为累加树（Greater Tree）执行过程## 初始 BST4/ \
1   6/ \5   7---## 初始状态
- `pre = 0`
- `cur = root (4)`
- 栈：`[]`---## 1️⃣ 第一次 while 循环
- `cur = 4` → 入栈  栈：`[4]`  `cur = 6`---## 2️⃣ 第二次 while 循环
- `cur = 6` → 入栈  栈：`[4, 6]`  `cur = 7`---## 3️⃣ 第三次 while 循环
- `cur = 7` → 入栈  栈：`[4, 6, 7]`  `cur = NULL`---## 4️⃣ 第四次 while 循环
- 出栈 `7`  `7 + pre(0) = 7` → 更新 `pre = 7`  树：4/ \
1   6/ \5   7`cur = NULL`---## 5️⃣ 第五次 while 循环
- 出栈 `6`  
`6 + pre(7) = 13` → 更新 `pre = 13`  
树：4/ \
1   13/  \5    7`cur = 5`---## 6️⃣ 第六次 while 循环
- `cur = 5` → 入栈  
栈：`[4, 5]`  
`cur = NULL`---## 7️⃣ 第七次 while 循环
- 出栈 `5`  
`5 + pre(13) = 18` → 更新 `pre = 18`  
树：4/ \
1   13/  \18    7`cur = NULL`---## 8️⃣ 第八次 while 循环
- 出栈 `4`  
`4 + pre(18) = 22` → 更新 `pre = 22`  
树：22/  \
1    13/  \18    7`cur = 1`---## 9️⃣ 第九次 while 循环
- `cur = 1` → 入栈  
栈：`[1]`  
`cur = NULL`---## 🔟 第十次 while 循环
- 出栈 `1`  
`1 + pre(22) = 23` → 更新 `pre = 23`  
树：
以此类推不过多赘述了。