题目描述
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如:
输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
解题思路
反序中序遍历的方法是通过递归实现。通过调用栈回到之前的节点,我们可以轻松地反序遍历所有节点。
在递归方法中,我们维护一些递归调用过程中可以访问和修改的全局变量。首先我们判断当前访问的节点是否存在,如果存在就递归右子树,递归回来的时候更新总和和当前点的值,然后递归左子树。如果我们分别正确地递归 root.right 和 root.left ,那么我们就能正确地用大于某个节点的值去更新此节点,然后才遍历比它小的值。
代码实现
/**
* 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;
}
};