62 lines
1.2 KiB
JavaScript
62 lines
1.2 KiB
JavaScript
/*
|
||
* @lc app=leetcode id=538 lang=javascript
|
||
*
|
||
* [538] Convert BST to Greater Tree
|
||
*
|
||
* https://leetcode.com/problems/convert-bst-to-greater-tree/description/
|
||
*
|
||
* algorithms
|
||
* Easy (50.04%)
|
||
* Total Accepted: 75.4K
|
||
* Total Submissions: 149K
|
||
* Testcase Example: '[5,2,13]'
|
||
*
|
||
* Given a Binary Search Tree (BST), convert it to a Greater Tree such that
|
||
* every key of the original BST is changed to the original key plus sum of all
|
||
* keys greater than the original key in BST.
|
||
*
|
||
*
|
||
* Example:
|
||
*
|
||
* Input: The root of a Binary Search Tree like this:
|
||
* 5
|
||
* / \
|
||
* 2 13
|
||
*
|
||
* Output: The root of a Greater Tree like this:
|
||
* 18
|
||
* / \
|
||
* 20 13
|
||
*
|
||
*
|
||
*/
|
||
/**
|
||
* 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 res = 0;
|
||
function r(root) {
|
||
if (root === null) return null;
|
||
|
||
r(root.right);
|
||
|
||
root.val += res;
|
||
|
||
res = +root.val;
|
||
|
||
r(root.left);
|
||
|
||
return root;
|
||
}
|
||
r(root);
|
||
return root;
|
||
};
|