1038. Binary Search Tree to Greater Sum Tree Medium

1/**
2 * [1038] Binary Search Tree to Greater Sum 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: 400px; height: 273px;" />
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 [1, 100].
26 * 	0 <= Node.val <= 100
27 * 	All the values in the tree are unique.
28 * 
29 *  
30 * Note: This question is the same as 538: <a href="https://leetcode.com/problems/convert-bst-to-greater-tree/" target="_blank">https://leetcode.com/problems/convert-bst-to-greater-tree/</a>
31 * 
32 */
33pub struct Solution {}
34use crate::util::tree::{TreeNode, to_tree};
35
36// problem: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
37// discuss: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41// Definition for a binary tree node.
42// #[derive(Debug, PartialEq, Eq)]
43// pub struct TreeNode {
44//   pub val: i32,
45//   pub left: Option<Rc<RefCell<TreeNode>>>,
46//   pub right: Option<Rc<RefCell<TreeNode>>>,
47// }
48// 
49// impl TreeNode {
50//   #[inline]
51//   pub fn new(val: i32) -> Self {
52//     TreeNode {
53//       val,
54//       left: None,
55//       right: None
56//     }
57//   }
58// }
59use std::rc::Rc;
60use std::cell::RefCell;
61impl Solution {
62    pub fn bst_to_gst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
63        Some(Rc::new(RefCell::new(TreeNode::new(0))))
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_1038() {
75    }
76}
77