这道题让我们将二叉搜索树转为较大树，通过题目汇总的例子可以明白，是把每个结点值加上所有比它大的结点值总和当作新的结点值。
二叉搜索树的定义：
BST 的定义：（二叉搜索树）
左子树的所有节点值都小于根节点；
右子树的所有节点值都大于根结点；
左右子树也是BST
可以知道，根结点转化后=根节点+所有右子树节点的和
那么，观察右子树，其根结点a转化后=根结点a+其所有右子树节点的和
以此类推，可以知道必须先对最后一个右子树处理
对于最后一个右子树，根结点b = b+右节点c；
右节点c = c；
左节点a = a+初始b+初始c。
也就是说，变量sum初始为0
1、先求原始值sum = c；
2、到根结点，sum = b+c，然后b = sum
3、到左节点，根结点、右节点都大于它，所以 sum = a+sum；a=sum
上面123所述，可以看出是右根左的中序遍历，因此有以下代码：
11.PNG
网友评论