【leetcode】538/1038: 把二叉搜索树转化为累加树

这题目乍一看就感觉特别简单,我首先想出了一个时间复杂度为O(n^2)的算法,也就是按照平常的方式进行中序遍历,每遇到一个node就在这个node后面继续往后进行中序遍历,得到其累加和。但是想了想完全可以从后往前进行中序遍历,这样只是多出了一个空间复杂度,需要多余的空间来储存sum变量,但是时间上就省了不少,解答的方法如下:

# 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 convertBST(self, root: TreeNode) -> TreeNode:
        self.al_sum=0
        def DFS(root):
            if root==None:
                return None
            DFS(root.right)
            self.al_sum=self.al_sum+root.val
            root.val=self.al_sum
            DFS(root.left)

        DFS(root)
        return root

 

上一篇:leetcode 538. 把二叉搜索树转换为累加树


下一篇:SQLServer 分布式查询MySQL