919. Complete Binary Tree Inserter Medium

1/**
2 * [919] Complete Binary Tree Inserter
3 *
4 * A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
5 * Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.
6 * Implement the CBTInserter class:
7 * 
8 * 	CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.
9 * 	int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.
10 * 	TreeNode get_root() Returns the root node of the tree.
11 * 
12 *  
13 * Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/lc-treeinsert.jpg" style="width: 500px; height: 143px;" />
15 * Input
16 * ["CBTInserter", "insert", "insert", "get_root"]
17 * [[[1, 2]], [3], [4], []]
18 * Output
19 * [null, 1, 2, [1, 2, 3, 4]]
20 * Explanation
21 * CBTInserter cBTInserter = new CBTInserter([1, 2]);
22 * cBTInserter.insert(3);  // return 1
23 * cBTInserter.insert(4);  // return 2
24 * cBTInserter.get_root(); // return [1, 2, 3, 4]
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	The number of nodes in the tree will be in the range [1, 1000].
30 * 	0 <= Node.val <= 5000
31 * 	root is a complete binary tree.
32 * 	0 <= val <= 5000
33 * 	At most 10^4 calls will be made to insert and get_root.
34 * 
35 */
36pub struct Solution {}
37use crate::util::tree::{TreeNode, to_tree};
38
39// problem: https://leetcode.com/problems/complete-binary-tree-inserter/
40// discuss: https://leetcode.com/problems/complete-binary-tree-inserter/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44// Definition for a binary tree node.
45// #[derive(Debug, PartialEq, Eq)]
46// pub struct TreeNode {
47//   pub val: i32,
48//   pub left: Option<Rc<RefCell<TreeNode>>>,
49//   pub right: Option<Rc<RefCell<TreeNode>>>,
50// }
51// 
52// impl TreeNode {
53//   #[inline]
54//   pub fn new(val: i32) -> Self {
55//     TreeNode {
56//       val,
57//       left: None,
58//       right: None
59//     }
60//   }
61// }
62struct CBTInserter {
63        vec![]
64    }
65
66
67/** 
68 * `&self` means the method takes an immutable reference.
69 * If you need a mutable reference, change it to `&mut self` instead.
70 */
71impl CBTInserter {
72
73    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
74        
75    }
76    
77    fn insert(&self, val: i32) -> i32 {
78        
79    }
80    
81    fn get_root(&self) -> Option<Rc<RefCell<TreeNode>>> {
82        
83    }
84}
85
86/**
87 * Your CBTInserter object will be instantiated and called as such:
88 * let obj = CBTInserter::new(root);
89 * let ret_1: i32 = obj.insert(val);
90 * let ret_2: Option<Rc<RefCell<TreeNode>>> = obj.get_root();
91 */
92
93// submission codes end
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_919() {
101    }
102}
103