leetcode 538. Convert BST to Greater Tree 二叉搜索树的中序遍历 + DFS

野性酷女 2022-06-03 03:39 108阅读 0赞

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:  
5  
/ \\  
2 13

Output: The root of a Greater Tree like this:  
18  
/ \\  
20 13

本题题意很简单，注意BST二叉搜索树的中序遍历得到的是一个有序序列，那么我们利用这个性质可以直接计算

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        int curSum = 0;
        TreeNode* convertBST(TreeNode* root)
        {
            dfs(root);
            return root;
        }
    
        void dfs(TreeNode* root)
        {
            if (root == NULL)
                return;
            else
            {
                dfs(root->right);
    
                curSum += root->val;
                root->val = curSum;
    
                dfs(root->left);
            }
        }
    };