LeetCode: 1038. Binary Search Tree to Greater Sum Tree

微信扫一扫,分享到朋友圈

LeetCode: 1038. Binary Search Tree to Greater Sum Tree

原题地址: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.

Example 1:

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Constraints:

  1. The number of nodes in the tree is between 1 and 100.
  2. Each node will have value between 0 and 100.
  3. The given tree is a binary search tree.

Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/

修改 BST,将每个节点的值修改为所有值比它大的节点值的总和。

从大到小遍历 BST,遍历过程中累加 value

中序遍历 BST 可以得到按从小到大排序的节点值有序数组,倒序遍历这个有序数组即可实现统计每个节点的所有比它大的值的总和。

也可以不用生成这个从小到大排序的有序数组,直接修改中序遍历改为按从大到小遍历 BST 即可。

按从大到小遍历 BST 的 Python 代码类似下面这样:

def order(root):
if root is None:
return
order(root.right)
# print(root)
order(root.left)

从大到小遍历 BST 并在遍历的过程中统计所有比当前节点的值大的节点的值的总和的方法的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def __init__(self):
self.sum_val = 0
def bstToGst(self, root):
if root is None:
return root
self.bstToGst(root.right)
root.val = root.val + self.sum_val
self.sum_val = root.val
self.bstToGst(root.left)
return root

腾讯AI Lab语音技术中心应用与研究介绍

上一篇

LeetCode: 108. Convert Sorted Array to Binary Search Tree

下一篇

你也可能喜欢

LeetCode: 1038. Binary Search Tree to Greater Sum Tree

长按储存图像,分享给朋友