538. Convert BST to Greater Tree Medium

1/**
2 * [538] Convert BST to Greater Tree
3 *
4 * Given the root of 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 the sum of all keys greater than the original key in BST.
5 * As a reminder, a binary search tree is a tree that satisfies these constraints:
6 * 
7 * 	The left subtree of a node contains only nodes with keys less than the node's key.
8 * 	The right subtree of a node contains only nodes with keys greater than the node's key.
9 * 	Both the left and right subtrees must also be binary search trees.
10 * 
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2019/05/02/tree.png" style="width: 500px; height: 341px;" />
14 * Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
15 * Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
16 * 
17 * Example 2:
18 * 
19 * Input: root = [0,null,1]
20 * Output: [1,null,1]
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	The number of nodes in the tree is in the range [0, 10^4].
26 * 	-10^4 <= Node.val <= 10^4
27 * 	All the values in the tree are unique.
28 * 	root is guaranteed to be a valid binary search tree.
29 * 
30 *  
31 * Note: This question is the same as 1038: <a href="https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/" target="_blank">https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/</a>
32 * 
33 */
34pub struct Solution {}
35use crate::util::tree::{TreeNode, to_tree};
36
37// problem: https://leetcode.com/problems/convert-bst-to-greater-tree/
38// discuss: https://leetcode.com/problems/convert-bst-to-greater-tree/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42// Definition for a binary tree node.
43// #[derive(Debug, PartialEq, Eq)]
44// pub struct TreeNode {
45//   pub val: i32,
46//   pub left: Option<Rc<RefCell<TreeNode>>>,
47//   pub right: Option<Rc<RefCell<TreeNode>>>,
48// }
49// 
50// impl TreeNode {
51//   #[inline]
52//   pub fn new(val: i32) -> Self {
53//     TreeNode {
54//       val,
55//       left: None,
56//       right: None
57//     }
58//   }
59// }
60use std::rc::Rc;
61use std::cell::RefCell;
62impl Solution {
63    pub fn convert_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
64        Some(Rc::new(RefCell::new(TreeNode::new(0))))
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_538() {
76    }
77}
78