LeetCode538将二叉查找树转化为积累树。
题目
给出二叉查找树的根节点，它有不同的节点值。请将其转换为更大和树，以便每个节点的新值等于原始树中大于或等于node.val的值之和。
提醒二叉查找树满足以下限制：
节点的左子树只包含键小于节点键的节点。
节点的右子树仅包含键大于该节点的键的节点。
左右子树也必须是二分搜索法树。
注：本问题同1038:3359 leet code-cn.com/problems/binary-search-tree-to-great-sum-tree/
例1:
输入：[4，1，6，0，2，5，7，null，null，3，null，null，8]
输出：[30，36，21，36，35，26，15，null，null，33，null，null，8]
例2:
输入：root=[0，null，1]
输出：[1，空，1]
例3:
输入：root=[1，0，2]
输出：[3，3，2]
例4:
输入：root=[3，2，4，1]
输出：[7，9，4，10]
提示：
树中的节点数介于0和104之间。
每个节点的值在-104和104之间。
树中的所有值都彼此不同。
给定的树是二叉查找树。
方法
递归法
时间复杂度：O(n)，其中n是二叉查找树的节点数。每个节点只遍历一次。
空间的复杂性：O(n)
解决方案类{
private int sum=0；
公共树节点转换器(树节点根){ 0
if(root！=null){ 0
convert BST(root . right)；
root.val=root.val总和；
sum=root.val
convert BST(root . left)；
}
返回根；
}
}
Morris 遍历
时间复杂度：O(n)，其中n是二叉查找树的节点数。每个节点只遍历一次。
空间的复杂性：O(1)
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/143787.html