1. 题目描述
给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如:
输入: 原始二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13
2. 解题思路
我们都知道二叉树的中序遍历结果是一个递增的数组。这里我们可以进行倒序进行中序遍历,这样遍历的出的数组就是递减的。
中序遍历的顺序是 左子树→根节点→右子树
所以可以先遍历右子树,再遍历根节点,最后遍历左子树。
这样的话,设置一个节点不断累加之前的值,那么在当前节点的值就会赋值成比他大的数的和。
3. 代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var convertBST = function(root) {
let sum = 0
const inOrder = (root) => {
if(!root){
return
}
if(root.right){
inOrder(root.right)
}
sum += root.val
root.val = sum
if(root.left){
inOrder(root.left)
}
}
inOrder(root)
return root
};