【算法思考记录】力扣1038. 从二叉搜索树到更大和树【C++,递归，中序遍历】

本文主要是介绍【算法思考记录】力扣1038. 从二叉搜索树到更大和树【C++,递归，中序遍历】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣1038. 从二叉搜索树到更大和树

从二叉搜索树到更大和树：理解中序位置的递归解法

问题概述

二叉搜索树（BST）是一种特殊的二叉树，它的每个节点都满足以下条件：

左子树的所有节点值小于当前节点值。
右子树的所有节点值大于当前节点值。

本文探讨的问题是：如何将BST的每个节点的值替换为树中大于或等于该节点值的所有节点值之和。

示例

例如，输入的BST为 [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]。

解题思路

解决这个问题的关键是利用BST的性质和中序遍历。中序遍历（左-根-右）BST时，我们可以按照节点值的升序访问每个节点。

逆中序遍历

为了获得大于或等于当前节点值的和，我们进行逆中序遍历（右-根-左），这样可以按照节点值的降序访问每个节点，也就是优先访问右子树中的大节点。

累加和更新

我们维护一个累加和 sum，遍历到每个节点时，将 sum 加上当前节点的值，然后更新当前节点的值为 sum。

代码解析

class Solution {
public:int sum = 0;void dfs(TreeNode *node) {if (node == nullptr) return;dfs(node->right); // 递归访问右子树sum += node->val; // 更新累加和node->val = sum;  // 更新节点值dfs(node->left);  // 递归访问左子树}TreeNode* bstToGst(TreeNode* root) {dfs(root); // 从根节点开始递归return root;}
};