【leetcode】538. Convert BST to Greater Tree

题目如下：

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

解题思路：一时卡壳了，只想出了一个很挫的方法，把所有节点的值都取出来，然后找出每个节点的所有比其大的值的和，这个值就是这个节点的值要加上的大小，最后再遍历一次树修改节点。

代码如下：

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    l = []

    dic = {}

    def traverse(self,node,mode):

        if node == None:

            return

        if mode == 1:

            self.l.append(node.val)

        else:

            node.val += self.dic[node.val]

        if node.left != None:

            self.traverse(node.left,mode)

        if node.right != None:

            self.traverse(node.right,mode)

    def convertBST(self, root):

        """

        :type root: TreeNode

        :rtype: TreeNode

        """

        self.l = []

        self.dic = {}

        self.traverse(root,1)

        ul = sorted(list(set(self.l)))

        total = 0

        for i in ul[::-1]:

            self.dic[i] = total

            total += i

        self.traverse(root, 0)

        return root

巴特西

【leetcode】538. Convert BST to Greater Tree

最新文章

热门文章