将二叉搜索树换为累加树(Python3)

zhenpy 2019-10-05

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

将二叉搜索树换为累加树(Python3)

解决思路:使用新的遍历方式(右子树,根、左子树)遍历整棵树。设置全局变量累加值,再逐一更新节点。

代码如下( ̄▽ ̄):

# 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)

时间与空间复杂度:

将二叉搜索树换为累加树(Python3)

链接:https://leetcode-cn.com/probl...

相关推荐