首页 > 代码库 > 538. Convert BST to Greater Tree 二叉搜索树转换为更大树

538. Convert BST to Greater Tree 二叉搜索树转换为更大树

2024-10-20 23:31:02   208人阅读

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
题意：给出二叉搜索树，每一个节点累加比自己更大的值
解法：根据二叉搜索树的特性可知，按照 右->根->左的顺序遍历节点
  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  10.     def convertBST(self, root):
  11.         """
  12.         :type root: TreeNode
  13.         :rtype: TreeNode
  14.         """
  15.         self.helper(root)
  16.         return root
  17.         
  18.         
  19.     sum = 0
  21.     def helper(self, node):
  22.         if(node):
  23.             self.helper(node.right)
  24.             node.val += self.sum
  25.             self.sum = node.val
  26.             self.helper(node.left)
  27.




来自为知笔记(Wiz)


538. Convert BST to Greater Tree 二叉搜索树转换为更大树


联系
我们