Greater Tree

发表于 | 分类于

Greater Tree

题目描述：

给定一颗二叉搜索树的头结点，将树中的每个节点变大；变大的规则在于：对于某个节点而言，找到树中大于该节点值的所有节点值的和，并将其加到该节点上。

例子：

这是leetcode上的题目

解题思路：

初看题目可能觉得比较麻烦，因为要找到所有的大于某个节点的和。但是注意题目中给定的：这棵树是二叉搜索树。我们可以利用右侧节点大于根节点；左侧节点小于根节点这个特性来解题。我们从最右侧节点开始，对于最右侧节点而言，其为最大，所以不需要改变；对于这个节点的父母节点我们需要将其右侧的节点的和加上即可；所以在遍历的过程中不断的将遍历的过程节点累加即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    int cur_sum = 0;
public:
    TreeNode* convertBST(TreeNode* root) {
        greater(root);
        return root;
        
    }
    void greater(TreeNode* &head){
        if (!head) return;
        if (head->right) greater(head->right);
        cur_sum += head->val;//计算累加和
        head->val = cur_sum;//将右侧的和加上到当前节点
        if (head->left) greater(head->left);
    }
};