538. Convert BST to Greater Tree

Leetcode link

解题思路

本题要求我们把一个 BST 的每个节点的值变成节点本身的值加上所有比它大的节点的值

仔细看题目给出的示例，可以看到这个节点的累加过程是

1. 右节点
2. 根节点
3. 左节点

所以我们可以用中序深度优先搜索来做这题，记得维护一个 sum 变量来保存之前累加的值就好

C++

class Solution {
 private:
  int sum = 0;

 public:
  void dfs(TreeNode* root) {
    if (!root) {
      return;
    }

    if (root->right) {
      dfs(root->right);
    }
    root->val = sum += root->val;
    if (root->left) {
      dfs(root->left);
    }
  }
  TreeNode* convertBST(TreeNode* root) {
    dfs(root);
    return root;
  }
};

Javascript

var convertBST = function(root) {
      // 如果用全局变量好像 leetcode 跑测试会有问题，就写进来了
    let sum = 0
    var dfs = function(root) {
    if(!root) {
        return;
    }

    if(root.right) {
        dfs(root.right);
    }
    root.val = sum+= root.val;
    if(root.left){
        dfs(root.left);
    }
}

    dfs(root);
    return root;
};