leetcode 538. Convert BST to Greater Tree

逃离我推掉我的手 2022-06-13 02:24 388阅读 0赞

# 1.题目 #

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

转换一棵二叉搜索树，转换规则：一个节点的值=所有比它大的节点值之和  
Example:

Input: The root of a Binary Search Tree like this:

5
            /   \
           2     13

Output: The root of a Greater Tree like this:

18
            /   \
          20     13

# 2.分析 #

考察中序遍历。从大到小遍历。BST的特点是左节点<根结点<右节点  
中序遍历，从大到小依次求和然后将值赋给当前遍历的节点。

# 3.代码 #

class Solution {
    public:
        void BST_inorder(TreeNode* root, int& sum) {
            if (root->right)
                BST_inorder(root->right,sum);
            root->val += sum;
            sum = root->val;
            if (root->left)
                BST_inorder(root->left, sum);
        }
        TreeNode* convertBST(TreeNode* root) {
            if(root==NULL)
                return root;
            int sum = 0;
            BST_inorder(root, sum);
            return root;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，388人围观）

还没有评论，来说两句吧...

相关阅读

相关（Java）leetcode-538 Convert BST to Greater Tree （把二叉搜索树转换为累加树）

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

痛定思痛。/ 2023年02月16日 04:24/ 0 赞/ 21 阅读

相关 Convert BST to Greater Tree（C++把二叉搜索树转换为累加树）

解题思路：（1）右中左遍历 / Definition for a binary tree node. struct TreeNode {

深碍√TFBOYSˉ_/ 2023年01月15日 11:26/ 0 赞/ 88 阅读

相关 LeetCode - Medium - 538. Convert BST to Greater Tree

Topic Tree Depth-first Search Binary Search Tree Recursion Description

超、凢脫俗/ 2022年10月05日 05:42/ 0 赞/ 4 阅读

相关 [leetcode]- 538. Convert BST to Greater Tree

刷这道题的时候，并没有想到中序遍历的方法，对于树的遍历算法应该去复习一下了没有思路，于是上网查找了一些解法，下面的解法简单机智。转载地址：[http://blog.csdn

浅浅的花香味﹌/ 2022年06月18日 04:25/ 0 赞/ 95 阅读

相关 leetcode 538. Convert BST to Greater Tree

1.题目 Given a Binary Search Tree (BST), convert it to a Greater Tree such that every k

逃离我推掉我的手/ 2022年06月13日 02:24/ 0 赞/ 389 阅读

相关 leetcode 538. Convert BST to Greater Tree 二叉搜索树的中序遍历 + DFS

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of th

野性酷女/ 2022年06月03日 03:39/ 0 赞/ 89 阅读

相关 538. Convert BST to Greater Tree

/ Created by Joe on 2018/1/17. 538. Convert BST to Greater Tree https://leetcode.

迈不过友情╰/ 2022年06月01日 02:49/ 0 赞/ 110 阅读

相关 LeetCode：538. Convert BST to Greater Tree（一棵树上加入所有的节点）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。 > > 这博客是记录我学习的点点滴滴，如果您对 Python、Java

╰+攻爆jí腚メ/ 2022年04月11日 14:16/ 0 赞/ 118 阅读

相关 leetcode------Convert Sorted Array to Binary Search Tree

<table style="width:348px;"> <tbody> <tr> <td>标题：</td> <td><a href="https:/

不念不忘少年蓝@/ 2021年12月16日 02:47/ 0 赞/ 143 阅读

相关 LeeCod : 538. Convert BST to Greater Tree 二叉搜索树转增大树

试题 Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key

约定不等于承诺〃/ 2021年06月24日 16:11/ 0 赞/ 499 阅读