題目
給出二叉搜索樹的根節(jié)點(diǎn)踪危，該樹的節(jié)點(diǎn)值各不相同朗涩，請(qǐng)你將其轉(zhuǎn)換為累加樹（Greater Sum Tree）愿待，使每個(gè)節(jié)點(diǎn) node 的新值等于原樹中大于或等于 node.val 的值之和糠惫。
例：
輸入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
輸出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
方法：遞歸
__ init __ 函數(shù)：
- pre 表示此時(shí)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
convertBST 函數(shù)：
- 調(diào)用 traversal 函數(shù)实撒，進(jìn)行遍歷
traversal 函數(shù)：右中左遍歷二叉樹
- 若節(jié)點(diǎn)為空姊途，則返回 None
- 根據(jù)二叉搜索樹和累加樹的定義可知，最右測的節(jié)點(diǎn)的值為其自身值知态，而最左側(cè)節(jié)點(diǎn)的值為整棵樹所有節(jié)點(diǎn)值的和捷兰。若將該二叉搜索樹的所有節(jié)點(diǎn)值按順序放入一個(gè)數(shù)組的話，每個(gè)節(jié)點(diǎn)的新節(jié)點(diǎn)值為其后一個(gè)節(jié)點(diǎn)值加上自身的節(jié)點(diǎn)值负敏。所以此處先遍歷右側(cè)后中間最后左側(cè)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def __init__(self):
self.pre = TreeNode()
def convertBST(self, root):
self.traversal(root)
return root
def traversal(self, node):
if not node:
return None
self.traversal(node.right)
node.val += self.pre.val
self.pre = node
self.traversal(node.left)
