Keshawn_lu's Blog

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

树
字数统计: 260阅读时长: 1 min
2020/09/21 Share

题目简介：

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

例如：

1
2
3
4
5
6
7
8
9
输入: 原始二叉搜索树:
              5
            /   \
           2     13
           
输出: 转换为累加树:
             18
            /   \
          20     13

思路：

一开始的想法是先将结点值都一个个保存下来，然后再遍历搜索累加，但是这样子很慢。

后来发现这是个二叉搜索树，那么可以利用反中序遍历，这样子遍历出来的元素值一定是递减的，所以定义一个sum用来累加遍历到的元素的值即可。

代码如下：

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
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    int sum = 0;

    void dfs(TreeNode* root){

        if(!root)
            return;
        
        dfs(root -> right);	//反中序遍历

        sum += root -> val;
        root -> val = sum;

        dfs(root -> left);
    }

    TreeNode* convertBST(TreeNode* root) {

        dfs(root);

        return root;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网