leetcode538题解

Convert BST to Greater Tree

题目描述：

将一颗二叉搜索树的每个比当前节点大的节点都与该节点求和，从而形成一颗更大的二叉树

题解：

由题意，我们可以得知是一颗二叉搜索树，而二叉搜索数又有什么特点呢？

1，左儿子一定小于根节点

2，右儿子一定大于根节点

所以我们可以推断出，最后一个右儿子节点一定是最大的，最后一个左儿子节点一定是最小的，所以我们可以从先对右儿子进行相加，然后依次与其他节点求和，下面展示一下code

int sum=0;

public staticTreeNodeconvertBST(TreeNode root) {

    convert(root);

    returnroot;

}

public voidconvert(TreeNode node) {

if(node ==null) {

    return;

}

convert(node.right);

node.val+=sum;

// 存储节点的值，供下次递归时使用

sum= node.val;

convert(node.left);

}