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

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

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

例如：

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

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

来源：力扣（LeetCode）
链接：538. Convert BST to Greater Tree

解题思路

考虑到是二叉搜索树，根据题意，其实就是将每个节点的值与其所有右边的节点值相加，这个正好和中序遍历相反，其实就是逆中序遍历的是你遍历到哪里，累加到哪里。

思路对了以后本题的代码就非常好写了，需要注意的是因为要求节点的值，需要带一个int*的指针变量来记录并修改各个节点累加变量的值，具体代码如下：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void helper(struct TreeNode* root, int* sum){
    if(!root) return;
    
    helper(root->right, sum);
    root->val += *sum;
    *sum = root->val;
    helper(root->left, sum);
}

struct TreeNode* convertBST(struct TreeNode* root){
    
    int sum = 0;
    helper(root, &sum);
    
    return root;
}