Leetcode538. 把二叉搜索树转换为累加树

2019-11-15  本文已影响0人  LonnieQ

题目

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

思路

中序遍历两遍,第一遍求和,第二遍把和赋予给当前节点,然后和减去当前节点值。

C++代码

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        calcuateSum(root);
        transferToGreaterTree(root);
        return root;
    }
    
    void calcuateSum(TreeNode* root) {
        if (root == NULL) return;
        calcuateSum(root->left);
        sum += root->val;
        calcuateSum(root->right);
    }
    void transferToGreaterTree(TreeNode* root) {
        if (root == NULL) return;
        transferToGreaterTree(root->left);
        int val = root->val;
        root->val = sum;
        sum -= val;
        transferToGreaterTree(root->right);
    }
};

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-bst-to-greater-tree

上一篇下一篇

猜你喜欢

热点阅读