2023-12-04每日一题

一、题目编号

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

二、题目链接

点击跳转到题目位置

三、题目描述

给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下， 二叉搜索树 满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

示例 1：

示例 2：

提示：

• 树中的节点数在 [1, 100] 范围内。
• 0 <= Node.val <= 100
• 树中的所有值均 不重复 。

四、解题代码

/**
 * 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 {
    vector<TreeNode*> iod;
    void dfs(TreeNode* root){
        if(root == nullptr){
            return;
        }
        dfs(root->left);
        iod.push_back(root);
        dfs(root->right);
    }

public:
    TreeNode* bstToGst(TreeNode* root) {
        dfs(root);
        for(int i = iod.size()-2; i >= 0; --i){
            iod[i]->val += iod[i+1]->val;
        }
    return root;
    }
};

五、解题思路

(1) 采用中序遍历即可。