将二叉搜索树换为累加树(Python3)
提出问题:给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
解决思路:使用新的遍历方式(右子树,根、左子树)遍历整棵树。设置全局变量累加值,再逐一更新节点。
代码如下( ̄▽ ̄):
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self): self.re = 0 def convertBST(self, root: TreeNode) -> TreeNode: if root==None: return root self.toBST(root) return root def toBST(self,node: TreeNode): if node==None: return else: self.toBST(node.right) node.val=node.val + self.re self.re = node.val self.toBST(node.left)
时间与空间复杂度:
相关推荐
chuckchen 2020-10-31
Will0 2020-10-12
Dreamhome 2020-10-09
xirongxudlut 2020-09-28
星辰大海的路上 2020-09-13
chaochao 2020-08-31
猪猪侠喜欢躲猫猫 2020-08-17
快递小可 2020-08-16
shengge0 2020-07-26
巩庆奎 2020-07-21
张文倩数据库学生 2020-07-19
xirongxudlut 2020-07-18
Ericbig 2020-07-18
kyelu 2020-07-09
liangzhouqu 2020-07-07
GuoSir 2020-06-28
chaigang 2020-06-27
pythonxuexi 2020-06-25