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