題目描述
給定一個二叉搜索樹（Binary Search Tree）著洼，把它轉(zhuǎn)換成為累加樹（Greater Tree)损话，使得每個節(jié)點(diǎn)的值是原來的節(jié)點(diǎn)值加上所有大于它的節(jié)點(diǎn)值之和宁赤。
例如：
輸入: 二叉搜索樹:
5
/ \
2 13
輸出: 轉(zhuǎn)換為累加樹:
18
/ \
20 13
解題思路
反序中序遍歷的方法是通過遞歸實(shí)現(xiàn)邑蒋。通過調(diào)用椏疗福回到之前的節(jié)點(diǎn)伐谈，我們可以輕松地反序遍歷所有節(jié)點(diǎn)。
在遞歸方法中民褂，我們維護(hù)一些遞歸調(diào)用過程中可以訪問和修改的全局變量茄菊。首先我們判斷當(dāng)前訪問的節(jié)點(diǎn)是否存在，如果存在就遞歸右子樹赊堪，遞歸回來的時候更新總和和當(dāng)前點(diǎn)的值面殖，然后遞歸左子樹。如果我們分別正確地遞歸 root.right 和 root.left 哭廉，那么我們就能正確地用大于某個節(jié)點(diǎn)的值去更新此節(jié)點(diǎn)脊僚，然后才遍歷比它小的值。
代碼實(shí)現(xiàn)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include<iostream>
using namespace std;
class Solution {
public:
void converBST_Helper(TreeNode* node, int& sum) {
if (node != nullptr) {
converBST_Helper(node->right, sum);
sum += node->val;
node->val = sum;
converBST_Helper(node->left, sum);
}
}
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (root != nullptr) {
converBST_Helper(root, sum);
}
return root;
}
};
