这题目乍一看就感觉特别简单,我首先想出了一个时间复杂度为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