-
Notifications
You must be signed in to change notification settings - Fork 21
/
_0538_ConvertBSTToGreaterTree.java
65 lines (60 loc) · 1.35 KB
/
_0538_ConvertBSTToGreaterTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package leetcode;
import util.TreeUtil.TreeNode;
/**
* @No
* @problem
* @level
* @desc
* @author liyazhou1
* @date 2019/09
*
* <pre>
* Given a Binary Search Tree (BST), convert it to a Greater Tree such that every val of the original BST is changed to the original val plus sum of all keys greater than the original val 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
* </pre>
*/
public class _0538_ConvertBSTToGreaterTree {
/**
* Note
*
* Thought
* 递归
*
* Challenge
*
* Algorithm
* 1.
* 2.
* 3.
*
* Complexity
* Time,
* Space,
*/
private static class Solution {
public TreeNode convertBST(TreeNode root) {
inorderVisit(root, new int[]{0});
return root;
}
private void inorderVisit(TreeNode root, int[] rightSum) {
if (root == null) {
return;
}
inorderVisit(root.right, rightSum);
root.val += rightSum[0];
rightSum[0] = root.val;
inorderVisit(root.left, rightSum);
}
}
}