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

╰+攻爆jí腚メ 2022-04-11 14:16 134阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方法1：

源码地址：

--------------------

### 题目描述： ###

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

例如：

输入: 原始二叉搜索树:
                  5
                /   \
               2     13
    
    输出: 转换为累加树:
                 18
                /   \
              20     13

来源：力扣（LeetCode）

--------------------

题意分析:  对如下只有三个节点的搜索二叉树而言，计算结果就是，右子节点保持不变，中间节点的值是其本身与右子节点相加的和，左子节点的值是其本身与中间节点、右子节点三者的累计之和。

也就是说，若求中间节点的值必须要先遍历完右子节点，而若求左子节点的值必须要遍历完中间节点和右子节点。因此，我们只需要进行一次反向中序遍历（即遍历顺序为右子树-->根节点-->左子树），在遍历过程中需要将已经遍历的节点的值进行累加，然后再赋值给当前节点。

**解题思路：**

1）定义一个全局变量sum，用于存储遍历的所有节点值的累计和；  
2）递归终止条件： root为空就返回null;  
3）递归右子树root.right;  
4）遍历当前节点，作如下操作：  
     将其值累加到sum中；  
     把sum赋值给当前节点的值；  
5）递归左子树root.left;

--------------------

### java实现方法1： ###

private int sum=0;
       /**
         * 转换搜索二叉树
         *
         * @param root 根节点
         * @return 输入结果
         */
        public TreeNode convertBST(TreeNode root) {
            if (root != null) {
                convertBST(root.right);
                sum += root.val;
                root.val = sum;
                convertBST(root.left);
            }
            return root;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方法1： ###

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    sum = 0
    
    
    def convert_bst(root: TreeNode) -> TreeNode:
        '''
            二分查找树
        Args:
            root: 根节点
        Returns:
            节点的值
        '''
        global sum
        if root != None:
            convert_bst(root.right)
            sum += root.val
            root.val = sum
            convert_bst(root.left)
        return root

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode