E-NR 538. Convert BST to Greater Tree
E
O(n), O(n):
写递归的时候尽量不要抠细节, 你相信你写的是对的, 逻辑上也合理, 那多半他就是对的.
'''
思路:
先读题.
题目可以转变为求解这样一个函数:
greater(root)使所有自己和自己children的 node.val + some_adder
因此, 对于每一个node来说,
greater_one_node(node) = node.val + its_adder
所以我们的代码中某个循环里, 一定会存在这样一段和上面等价的代码(这段话不理解没关系, 继续往下看):
node.val += adder
现在我们的目标转变成了, 弄清楚如何计算每个node对应的adder.
而这个adder, 题目说了就是所有比node大的其他node的val和.
因此, 对于每一个node来说,
greater_one_node(node) = node.val + sum_of_greatrt_node_val_of(node)
所以我们要弄清楚:
哪些node比当前node的val大? 这个问题不够清晰, 我们细化一下:
即, 如何找到这些比当前node的val大的node? 再具体一点:
即, 如何遍历才能找到这些比当前node的val大的node?
此时我们注意BST的一个性质:
对BST中序遍历(即LDR,左中右)输出顺序为一个递增序列(因为BST中每个node比自己所有
右子树上节点小, 比所有左子树节点大, 而LDR是先遍历左子树, 接着到自己, 再到右子树.)
||
||
||
\ /
\/
反过来想, 如果我们对BST反着中序遍历(reverse inorder traverse, 即RDL, 右中左), 我们
能得到一个递减序列. 我们惊喜的发现!! RDL可以遍历到所有比当前node的val大的node. 而我们自
然可以在遍历的过程中, 记录下所有比当前node的val大的node的val和, 即上文所述的adder,
我们可以先写下此算法中RDL的框架(有纰漏):
rdl(node):
if node:
rdl(node.right)
node.val += adder
rld(node.left)
而我们发现, 这个adder肯定要在递归里不断传递, 并且不断修改的, 所以我们稍微修改一下:
rdl(node, adder):
if node:
adder = rdl(node.right, adder)
modify adder here? or maybe ==========
node.val += adder ||
modify adder here? <=============
adder = rld(node.left, adder)
return adder
如何modify这个adder呢? 回到adder的本质, 即所有比node大的其他node的val和.
我们从最简单的情况开始考虑,
0. 对于BST中最大的node_0来说, 他的adder是0, 因为没有node比他大.
adder(node_0) = 0 (this is the base case)
1. 对于第二大的node_1来说, 他的adder是node_0+0,
adder(node_1) = node_0 + 0
= node_0 + adder(node_0)
2. 对于第三大的node_2来说, 他的adder是node_1+node_0
adder(node_2) = node_1 + node0 + 0
= node_1 + adder(node_1)
3. adder(node_3) = node_2 + node_1 + node_0 + 0
= node_2 + adder(node_2)
...
n. adder(node_n) = node_(n-1) + node_(n-2) + ... + node_0
= node_(n-1) + adder(node_(n-1))
递归在运行的时候, 先从n到0, 再从0到n.
我们观察从0到n这一步(即adder逐层返回)
发现要返回给上一层(比如从处理node_1的一层返回给处理node_2的一层)的adder, 需要
在本层, 用本层的adder(node)加上自身(而这个结果, 恰好就是我们题目中需要拿到的
greater之后的值), 作为新的adder返回给上一层. 即:
rdl(node, adder):
if node:
adder = rdl(node.right, adder)
node.val += adder
adder = node.val
adder = rld(node.left, adder)
return adder
接着我们在主函数convertBST调用这个rdl即可.
嗷嗷嗷嗷好累啊我死了!!
'''
# 1 lc标答, 思路和上面一样, 更简洁
class Solution(object):
def __init__(self):
self.total = 0
def convertBST(self, root):
if root is not None:
self.convertBST(root.right)
self.total += root.val
root.val = self.total
self.convertBST(root.left)
return root
# 我的答案:
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.r_rdl(root, 0)
return root
def r_rdl(self, root, adder):
if root:
adder = self.r_rdl(root.right, adder)
root.val += adder
adder = root.val
adder = self.r_rdl(root.left, adder)
return adder
# 或者另一种和上面完全等价的写法:
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.ldr(root, 0)
return root
def ldr(self, root, adder):
if not root:
return adder
else:
adder = self.ldr(root.right, adder)
root.val += adder
adder = root.val
adder = self.ldr(root.left, adder)
return adder
# 2
'''
在非__init__函数中声明instance variable(但是个人建议不要这么操作,感觉不太规范,应该在init里初始化)
下面例子只是方便理解答案里面的代码(虽然个人认为这个代码并不是什么规范的代码..)
class Solution(object):
def convertBST(self):
self.cur_sum = 0
a=Solution()
print(a.cur_sum) # AttributeError: 'Solution' object has no attribute
# 'cur_sum' on line x in main.py
print(a.__dict__.keys()) # ['__dict__']
a.convertBST()
print(a.__dict__.keys()) # ['__dict__', 'cur_sum']
print(a.cur_sum) # 0
'''
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.cur_sum = 0
self.convertHelper(root)
return root
def convertHelper(self, root):
if not root:
return
self.convertHelper(root.right)
root.val += self.cur_sum
self.cur_sum = root.val
self.convertHelper(root.left)NR 非递归解法:
NR Reverse Morris In-order Traversal
Last updated
Was this helpful?