leetcode_test_utils/tree/diagnosis.rs
1//! Most utilities for operating on [`TreeNode`].
2
3use std::cell::RefCell;
4use std::cmp::{max, Ordering};
5use std::collections::VecDeque;
6use std::fmt::{Display, Formatter, Write};
7use std::rc::Rc;
8
9use super::raw_def::TreeNode;
10use super::shortcuts::{new_cell, new_node, new_rc, to_ptr, val as pointed};
11
12pub type TreeHandle = Option<Rc<RefCell<TreeNode>>>;
13
14/// The classic traversal types of binary tree.
15#[derive(Ord, PartialOrd, Eq, PartialEq, Debug, Clone)]
16pub enum TraversalType {
17 /// pre-order
18 PreOrder,
19 /// in-order
20 InOrder,
21 /// post-order
22 PostOrder,
23 /// level order
24 LevelOrder,
25 // Rev...
26}
27
28#[derive(Debug, Eq, PartialEq)]
29/// Error when constructing a binary tree.
30pub enum TreeError {
31 /// The tree structure cannot be determined by given two order.
32 /// Theoretically, if every value occurs no more than once, a binary tree can be determined
33 /// iif its in-order and another(pre-order, post-order or level-order) sequence are provided.
34 ///
35 /// Note that in some special cases a tree can also be determined(eg., pre-order and post-order
36 /// both are "\[1\]"), but these cases are not handled and the corresponding `Nondeterministic`
37 /// error will be returned.
38 Nondeterministic(TraversalType, TraversalType),
39 /// Parsing leetcode-format tree failed. It is either because you miss the square bracket, or
40 /// if there is an element split by "," that cannot be parsed to [`i32`].
41 LeetcodeFormatError,
42}
43
44impl Display for TreeError {
45 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
46 match self {
47 Self::Nondeterministic(t1, t2) => f.write_fmt(format_args!(
48 "tree structure cannot be determined by `{:?}` and `{:?}`",
49 t1, t2
50 )),
51 Self::LeetcodeFormatError => f.write_str("leetcode format error"),
52 }
53 }
54}
55
56/// Associated function set for creating a binary tree.
57pub struct TreeBuilder;
58
59impl TreeBuilder {
60 /// Build a binary tree using the parsed format in leetcode.
61 ///
62 /// Returns the root of the binary tree specified in `values`.
63 ///
64 /// # Safety
65 ///
66 /// You must make sure the `values` does be the valid input sequence of a binary tree, or the
67 /// behaviour is undefined.
68 ///
69 /// # Examples
70 ///
71 /// ```
72 /// use leetcode_test_utils::tree::TreeBuilder;
73 /// use leetcode_test_utils::btree;
74 ///
75 /// let t1 = TreeBuilder::from_leetcode(&[]);
76 /// assert_eq!(t1, btree!());
77 ///
78 /// let t2 = TreeBuilder::from_leetcode(&[Some(1), None, Some(2)]);
79 /// assert_eq!(t2, btree!(1, null, 2));
80 /// ```
81 pub fn from_leetcode(values: &[Option<i32>]) -> TreeHandle {
82 if values.is_empty() {
83 return None;
84 }
85 let root = new_node(unsafe { (*values.get_unchecked(0)).unwrap() });
86 let mut q: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::with_capacity(4); // avoid early frequent allocations
87 q.push_back(Rc::clone(root.as_ref().unwrap())); // the `root` is always a `Rc`.
88
89 for arr in values[1..].chunks(2) {
90 let cur_head = q.pop_front().unwrap();
91 unsafe {
92 // safety: chunks(2) will always yield slice with len in {1, 2}.
93 if let Some(left_child_val) = *arr.get_unchecked(0) {
94 let core = new_rc(left_child_val);
95 q.push_back(Rc::clone(&core));
96 // safety: always valid pointer
97 (*cur_head.as_ptr()).left = Some(core);
98 }
99 if arr.len() == 2 {
100 if let Some(right_child_val) = *arr.get_unchecked(1) {
101 let core = new_rc(right_child_val);
102 q.push_back(Rc::clone(&core));
103 // safety: always valid pointer
104 (*cur_head.as_ptr()).right = Some(core);
105 }
106 }
107 }
108 }
109 root
110 }
111
112 /// Build a binary tree using the raw format in leetcode(see [Leetcode binary tree representation](https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-)).
113 ///
114 /// Returns the root of the binary tree specified in `s`, or [`Err`] indicating the parsing
115 /// error.
116 ///
117 /// # Safety
118 ///
119 /// You must make sure that the parsed pure sequence does be the valid binary tree, or the
120 /// behaviour is undefined.
121 ///
122 /// # Examples
123 ///
124 /// ```
125 /// use leetcode_test_utils::tree::TreeBuilder;
126 /// use leetcode_test_utils::btree;
127 /// use leetcode_test_utils::tree::diagnosis::TreeError;
128 ///
129 /// let t1 = TreeBuilder::from_leetcode_raw("[]");
130 /// assert_eq!(t1, Ok(btree!()));
131 ///
132 /// let t2 = TreeBuilder::from_leetcode_raw("[1,null,2]");
133 /// assert_eq!(t2, Ok(btree!(1, null, 2)));
134 ///
135 /// let t3 = TreeBuilder::from_leetcode_raw("(1,null,2)");
136 /// assert_eq!(t3.unwrap_err(), TreeError::LeetcodeFormatError);
137 ///
138 /// let t4 = TreeBuilder::from_leetcode_raw("[1,none,2]");
139 /// assert_eq!(t4.unwrap_err(), TreeError::LeetcodeFormatError);
140 ///
141 /// let t5 = TreeBuilder::from_leetcode_raw("[1,12345678901,3]"); // '12345678901' overflows i32
142 /// assert_eq!(t5.unwrap_err(), TreeError::LeetcodeFormatError);
143 /// ```
144 pub fn from_leetcode_raw(s: &str) -> Result<TreeHandle, TreeError> {
145 if let [left_bracket, nums @ .., right_bracket] = s.as_bytes() {
146 if *left_bracket != b'[' || *right_bracket != b']' {
147 return Err(TreeError::LeetcodeFormatError);
148 }
149 if nums.is_empty() {
150 return Ok(None);
151 }
152 let mut v = Vec::with_capacity(4);
153 for n in unsafe { std::str::from_utf8_unchecked(nums) }.split(',') {
154 if n == "null" {
155 v.push(None);
156 } else {
157 match n.parse::<i32>() {
158 Ok(i) => v.push(Some(i)),
159 Err(_) => return Err(TreeError::LeetcodeFormatError),
160 }
161 }
162 }
163 v.shrink_to_fit();
164 Ok(Self::from_leetcode(&v))
165 } else {
166 Err(TreeError::LeetcodeFormatError)
167 }
168 }
169
170 /// Build a binary tree with two specified orders and their sequences respectively.
171 ///
172 /// A binary tree(no value occurs more than once) can be built with in-order and another order
173 /// (say, pre-order, post-order or level order). This function builds the corresponding tree.
174 /// If the two types are not legal, or any invariance is compromised, returns an `Err`.
175 ///
176 /// This function is used when `seq1_type` or/and `seq2_type` is determined at runtime. If the types
177 /// can be determined at compile time, use [`Self::from_pre_in`], [`Self::from_post_in`] or
178 /// [`Self::from_level_in`] instead.
179 ///
180 /// # Arguments
181 ///
182 /// - `seq1_type` is the sequence type of `seq1`.
183 /// - `seq2_type` is the sequence type of `seq2`.
184 ///
185 /// # Examples
186 ///
187 /// ```
188 /// use leetcode_test_utils::tree::diagnosis::TraversalType;
189 /// use leetcode_test_utils::tree::{TreeBuilder, T};
190 /// use leetcode_test_utils::btree;
191 ///
192 /// let arg = 1;
193 /// let type1 = match arg{ // determined at runtime
194 /// 1 => TraversalType::PreOrder,
195 /// 2 => TraversalType::PostOrder,
196 /// _ => TraversalType::LevelOrder,
197 /// };
198 /// let type2 = TraversalType::InOrder;
199 ///
200 /// let seq1 = vec![1, 4, 2, 8, 5, 7]; // also at runtime
201 /// let seq2 = vec![4, 2, 1, 5, 7, 8];
202 ///
203 /// let tree = TreeBuilder::from_twos(type1, &seq1, type2, &seq2).unwrap();
204 /// let target = btree!(1, 4, 8, null, 2, 5, null, null, null, null, 7);
205 /// assert_eq!(tree, btree!(1, 4, 8, null, 2, 5, null, null, null, null, 7));
206 /// ```
207 pub fn from_twos(
208 seq1_type: TraversalType,
209 seq1: &[i32],
210 seq2_type: TraversalType,
211 seq2: &[i32],
212 ) -> Result<TreeHandle, TreeError> {
213 use TraversalType::*;
214 match (seq1_type, seq2_type) {
215 (PreOrder, InOrder) => Ok(Self::from_pre_in(seq1, seq2)),
216 (InOrder, PreOrder) => Ok(Self::from_pre_in(seq2, seq1)),
217 (PostOrder, InOrder) => Ok(Self::from_post_in(seq1, seq2)),
218 (InOrder, PostOrder) => Ok(Self::from_post_in(seq2, seq1)),
219 (LevelOrder, InOrder) => Ok(Self::from_level_in(seq1, seq2)),
220 (InOrder, LevelOrder) => Ok(Self::from_level_in(seq2, seq1)),
221 (o1, o2) => Err(TreeError::Nondeterministic(o1, o2)),
222 }
223 }
224
225 /// Build a tree using pre-order and in-order structures.
226 ///
227 /// Returns the corresponding binary tree, or panics if some invariance is violated(a value occurs
228 /// more than once, or pre_order.len() != in_order.len()).
229 ///
230 /// # Examples
231 /// ```
232 /// use leetcode_test_utils::btree;
233 /// use leetcode_test_utils::tree::TreeBuilder;
234 ///
235 /// let tree = TreeBuilder::from_pre_in(&[2, 1, 3], &[1, 2, 3]);
236 /// assert_eq!(tree, btree!(2, 1, 3));
237 /// ```
238 #[inline]
239 pub fn from_pre_in(pre_order: &[i32], in_order: &[i32]) -> TreeHandle {
240 assert_eq!(pre_order.len(), in_order.len(), "invariance violated");
241 // fixme: replaced the recursion with iteration
242 if pre_order.is_empty() {
243 return None;
244 }
245 let value = unsafe { *pre_order.get_unchecked(0) };
246 let pos = in_order
247 .iter()
248 .position(|&v| v == value)
249 .expect("invariance violated");
250 let ret = new_rc(unsafe { *in_order.get_unchecked(pos) });
251 // fixme: replaced with raw pointer op?
252 ret.borrow_mut().left = Self::from_pre_in(&pre_order[1..=pos], &in_order[..pos]);
253 ret.borrow_mut().right = Self::from_pre_in(&pre_order[pos + 1..], &in_order[pos + 1..]);
254 Some(ret)
255 }
256
257 /// Build a tree using post-order and in-order structures.
258 ///
259 /// Returns the corresponding binary tree, or panics if some invariance is violated(a value occurs
260 /// more than once, or post_order.len() != in_order.len()).
261 ///
262 /// # Examples
263 /// ```
264 /// use leetcode_test_utils::btree;
265 /// use leetcode_test_utils::tree::TreeBuilder;
266 ///
267 /// let tree = TreeBuilder::from_post_in(&[1, 3, 2], &[1, 2, 3]);
268 /// assert_eq!(tree, btree!(2, 1, 3));
269 /// ```
270 pub fn from_post_in(post_order: &[i32], in_order: &[i32]) -> TreeHandle {
271 assert_eq!(post_order.len(), in_order.len(), "invariance violated");
272 // fixme: replaced the recursion with iteration
273 if let Some((&value, post_order)) = post_order.split_last() {
274 let pos = in_order
275 .iter()
276 .position(|&v| v == value)
277 .expect("invariance violated");
278 let ret = new_rc(unsafe { *in_order.get_unchecked(pos) });
279 // fixme: replaced with raw pointer op?
280 ret.borrow_mut().left = Self::from_post_in(&post_order[..pos], &in_order[..pos]);
281 ret.borrow_mut().right = Self::from_post_in(&post_order[pos..], &in_order[pos + 1..]);
282 Some(ret)
283 } else {
284 None
285 }
286 }
287
288 /// Build a tree using level order and in-order structures.
289 ///
290 /// Returns the corresponding binary tree, or panics if some invariance is violated(a value occurs
291 /// more than once, or level_order.len() != in_order.len()).
292 ///
293 /// # Examples
294 /// ```
295 /// use leetcode_test_utils::btree;
296 /// use leetcode_test_utils::tree::TreeBuilder;
297 ///
298 /// let tree = TreeBuilder::from_level_in(&[1, 4, 8, 2, 5, 7], &[4, 2, 1, 5, 7, 8]);
299 /// assert_eq!(tree, btree!(1, 4, 8, null, 2, 5, null, null, null, null, 7));
300 /// ```
301 #[inline]
302 pub fn from_level_in(level_order: &[i32], in_order: &[i32]) -> TreeHandle {
303 assert_eq!(level_order.len(), in_order.len(), "invariance violated");
304 pub fn from_level_in_inner(level_order: &[i32], in_order: &[i32]) -> TreeHandle {
305 if in_order.is_empty() {
306 return None;
307 }
308 let (level_index, pos, value) = 'outer: loop {
309 for (level_index, &level_value) in level_order.iter().enumerate() {
310 for (in_index, &in_value) in in_order.iter().enumerate() {
311 if level_value == in_value {
312 break 'outer (level_index, in_index, level_value);
313 }
314 }
315 }
316 panic!("invariance violated!");
317 };
318 let cell = new_cell(value);
319 // fixme: replaced with raw pointer op?
320 cell.borrow_mut().left =
321 from_level_in_inner(&level_order[level_index + 1..], &in_order[..pos]);
322 cell.borrow_mut().right =
323 from_level_in_inner(&level_order[level_index + 1..], &in_order[pos + 1..]);
324 Some(Rc::new(cell))
325 }
326 from_level_in_inner(level_order, in_order)
327 }
328}
329
330/// Zero cost wrapper for [`Option<Rc<RefCell<TreeNode>>>`], also for bypassing the orphan rule.
331/// There are many useful methods for operating on the binary tree as well.
332#[derive(Debug, Clone)]
333pub struct T(pub TreeHandle);
334
335impl T {
336 /// Get the height for the binary tree.
337 ///
338 /// Returns the height of the binary tree. The empty tree has height 0.
339 ///
340 /// # Examples
341 ///
342 /// ```
343 /// use leetcode_test_utils::btree;
344 /// use leetcode_test_utils::tree::T;
345 ///
346 /// let tree1 = btree!(1, 2, 3);
347 /// assert_eq!(T(tree1).height(), 2);
348 /// assert_eq!(T(None).height(), 0);
349 /// ```
350 #[inline]
351 pub fn height(&self) -> usize {
352 unsafe { Self::height_maybe_null(to_ptr(self.0.as_ref())) }
353 }
354
355 /// Returns the height of the binary tree with given pointer as its root.
356 #[inline]
357 unsafe fn height_maybe_null(root: *const TreeNode) -> usize {
358 if root.is_null() {
359 0
360 } else {
361 Self::height_nonnull(root)
362 }
363 }
364
365 /// Returns the height of the binary tree with given non-null pointer as its root.
366 unsafe fn height_nonnull(root: *const TreeNode) -> usize {
367 let mut stk = Vec::with_capacity(4);
368 stk.set_len(1);
369 *stk.get_unchecked_mut(0) = (root, 1);
370 let mut max_height = 1_usize;
371 while !stk.is_empty() {
372 let (cur_node, h) = stk.pop().unwrap();
373 max_height = max(max_height, h);
374 if let Some(rc) = &(*cur_node).right {
375 stk.push((rc.as_ptr(), h + 1));
376 }
377 if let Some(rc) = &(*cur_node).left {
378 stk.push((rc.as_ptr(), h + 1));
379 }
380 }
381 max_height
382 }
383
384 /// Returns the pre-order of the binary tree.
385 pub fn pre_order(&self) -> Vec<i32> {
386 if let Some(ref rc) = self.0 {
387 let mut v = Vec::with_capacity(4);
388 let mut ret = Vec::with_capacity(4);
389 unsafe {
390 v.set_len(1);
391 *v.get_unchecked_mut(0) = rc.as_ptr() as *const TreeNode;
392 }
393 while !v.is_empty() {
394 let top = v.pop().unwrap();
395 ret.push(pointed(top));
396 if let Some(rc) = unsafe { &(*top).right } {
397 v.push(rc.as_ptr());
398 }
399 if let Some(rc) = unsafe { &(*top).left } {
400 v.push(rc.as_ptr());
401 }
402 }
403 ret.shrink_to_fit();
404 ret
405 } else {
406 Default::default()
407 }
408 }
409
410 /// Returns the in-order of the binary tree.
411 #[inline]
412 pub fn in_order(&self) -> Vec<i32> {
413 // fixme: remove the recursion
414 fn in_order_inner(root: *const TreeNode, v: &mut Vec<i32>) {
415 if let Some(rc) = unsafe { &(*root).left } {
416 in_order_inner(rc.as_ptr(), v);
417 }
418 v.push(pointed(root));
419 if let Some(rc) = unsafe { &(*root).right } {
420 in_order_inner(rc.as_ptr(), v);
421 }
422 }
423 if let Some(ref rc) = self.0 {
424 let mut v = Vec::with_capacity(4);
425 in_order_inner(rc.as_ptr(), &mut v);
426 v.shrink_to_fit();
427 v
428 } else {
429 Default::default()
430 }
431 }
432
433 /// Returns the post-order of the binary tree.
434 pub fn post_order(&self) -> Vec<i32> {
435 // fixme: remove the recursion
436 fn post_order_inner(root: *const TreeNode, v: &mut Vec<i32>) {
437 if let Some(rc) = unsafe { &(*root).left } {
438 post_order_inner(rc.as_ptr(), v);
439 }
440 if let Some(rc) = unsafe { &(*root).right } {
441 post_order_inner(rc.as_ptr(), v);
442 }
443 v.push(pointed(root));
444 }
445 if let Some(ref rc) = self.0 {
446 let mut v = Vec::with_capacity(4);
447 post_order_inner(rc.as_ptr(), &mut v);
448 v.shrink_to_fit();
449 v
450 } else {
451 Default::default()
452 }
453 }
454
455 /// Returns the level order of the binary tree.
456 pub fn level_order(&self) -> Vec<i32> {
457 if let Some(ref rc) = self.0 {
458 let mut q = VecDeque::with_capacity(4);
459 q.push_back(rc.as_ptr() as *const TreeNode);
460 let mut v = Vec::with_capacity(4);
461 while !q.is_empty() {
462 let top = q.pop_front().unwrap();
463 v.push(pointed(top));
464 if let Some(rc) = unsafe { &(*top).left } {
465 q.push_back(rc.as_ptr());
466 }
467 if let Some(rc) = unsafe { &(*top).right } {
468 q.push_back(rc.as_ptr());
469 }
470 }
471 v.shrink_to_fit();
472 v
473 } else {
474 Default::default()
475 }
476 }
477 /// Launder the binary tree.
478 ///
479 /// Replace the current binary tree with a new representation, in which the structure and values is
480 /// preserved respectively, but every reachable [`Rc`] will only have 1 strong count.
481 ///
482 /// This is helpful if you do not want the value in your tree changed through
483 /// [`Rc<RefCell<TreeNode>>`] elsewhere.
484 ///
485 /// # Examples
486 ///
487 /// ```
488 /// use leetcode_test_utils::btree;
489 /// use leetcode_test_utils::tree::T;
490 /// use std::rc::Rc;
491 ///
492 /// let tree = T(btree!(3));
493 /// let evil = Rc::clone(tree.0.as_ref().unwrap());
494 /// // the action below changes the value handled in `tree`, which may be unexpected
495 /// evil.borrow_mut().val = 42;
496 /// assert_ne!(tree.0.unwrap().borrow().val, 3);
497 /// ```
498 #[inline]
499 pub fn re_owned(&mut self) {
500 self.0 = self.detach().0;
501 }
502
503 /// Get the mirror tree.
504 ///
505 /// Returns a binary tree sharing the same structure and values handled by `self` except that
506 /// every reachable [`Rc`] will only have 1 strong count.
507 ///
508 /// This is helpful if you want to get the tree structure without worrying about the values be soon
509 /// changed by code elsewhere.
510 ///
511 /// # Examples
512 ///
513 /// ```
514 /// use leetcode_test_utils::btree;
515 /// use leetcode_test_utils::tree::T;
516 /// use std::rc::Rc;
517 ///
518 /// let tree = T(btree!(3));
519 /// let cannot_invade = tree.detach();
520 /// cannot_invade.0.as_ref().unwrap().borrow_mut().val = 42;
521 /// assert_eq!(tree.0.unwrap().borrow().val, 3);
522 /// ```
523 pub fn detach(&self) -> Self {
524 // fixme: needs more efficient algorithm
525 let v1 = self.pre_order();
526 let v2 = self.in_order();
527 Self(TreeBuilder::from_pre_in(&v1, &v2))
528 }
529
530 /// Test if the binary tree is balanced.
531 ///
532 /// # Example
533 ///
534 /// ```
535 /// use leetcode_test_utils::btree;
536 /// use leetcode_test_utils::tree::T;
537 ///
538 /// let tree1 = T(btree!(4, 2));
539 /// assert!(tree1.is_balanced());
540 ///
541 /// let tree2 = T(btree!(4, 2, null, 1));
542 /// assert!(!tree2.is_balanced())
543 /// ```
544 #[inline]
545 pub fn is_balanced(&self) -> bool {
546 fn is_balanced_inner(root: *const TreeNode) -> bool {
547 if !root.is_null() {
548 let left_ptr = to_ptr(unsafe { (*root).left.as_ref() });
549 let right_ptr = to_ptr(unsafe { (*root).right.as_ref() });
550 let mut h1 = unsafe { T::height_maybe_null(left_ptr) };
551 let mut h2 = unsafe { T::height_maybe_null(right_ptr) };
552 if h1 < h2 {
553 std::mem::swap(&mut h1, &mut h2);
554 }
555 h1 - h2 <= 1 && is_balanced_inner(left_ptr) && is_balanced_inner(right_ptr)
556 } else {
557 true
558 }
559 }
560 is_balanced_inner(to_ptr(self.0.as_ref()))
561 }
562
563 /// Test if the binary tree is a BST(binary search tree).
564 ///
565 /// # Examples
566 ///
567 /// ```
568 /// use leetcode_test_utils::btree;
569 /// use leetcode_test_utils::tree::T;
570 ///
571 /// let tree = T(btree!(5, 2, 9, 1));
572 /// assert!(tree.is_binary_search_tree());
573 /// ```
574 #[inline]
575 pub fn is_binary_search_tree(&self) -> bool {
576 // fixme: potential inefficient
577 self.in_order()
578 .windows(2)
579 .all(|tp| unsafe { tp.get_unchecked(0).cmp(tp.get_unchecked(1)) } == Ordering::Less)
580 }
581
582 /// Returns the leetcode representation of the handled binary tree.
583 ///
584 /// # Examples
585 ///
586 /// ```
587 /// use leetcode_test_utils::tree::T;
588 /// use leetcode_test_utils::btree;
589 ///
590 /// let tree = T(btree!(2, 4, null, 9));
591 /// assert_eq!(tree.to_leetcode_raw(), "[2,4,null,9]");
592 /// ```
593 pub fn to_leetcode_raw(&self) -> String {
594 let mut s = String::with_capacity(2);
595 unsafe {
596 let m = s.as_mut_vec();
597 m.set_len(1);
598 *m.get_unchecked_mut(0) = b'[';
599 }
600 debug_assert_eq!(s, "[");
601 for o in self.to_leetcode() {
602 if let Some(i) = o {
603 s.write_fmt(format_args!("{},", i))
604 .expect("String::write_fmt() failed");
605 } else {
606 s.write_str("null,").expect("String::write_fmt() failed");
607 }
608 }
609 let pos = s.as_bytes().len() - 1;
610 unsafe {
611 *s.as_mut_vec().get_unchecked_mut(pos) = b']';
612 }
613 s.shrink_to_fit();
614 s
615 }
616
617 /// Returns the parsed leetcode representation of the handled binary tree.
618 ///
619 /// # Examples
620 ///
621 /// ```
622 /// use leetcode_test_utils::tree::T;
623 /// use leetcode_test_utils::btree;
624 ///
625 /// let tree = T(btree!(2, 4, null, 9));
626 /// assert_eq!(tree.to_leetcode(), vec![Some(2), Some(4), None, Some(9)]);
627 /// ```
628 pub fn to_leetcode(&self) -> Vec<Option<i32>> {
629 if let Some(ref rc) = self.0 {
630 let root = rc.as_ptr() as *const TreeNode;
631 let mut ans = Vec::with_capacity(4);
632 let mut q = VecDeque::with_capacity(4);
633 q.push_back(root);
634 while !q.is_empty() {
635 let top = q.pop_front().unwrap();
636 if top.is_null() {
637 ans.push(None);
638 } else {
639 ans.push(Some(pointed(top)));
640 q.push_back(to_ptr(unsafe { (*top).left.as_ref() }));
641 q.push_back(to_ptr(unsafe { (*top).right.as_ref() }));
642 }
643 }
644 ans.truncate(ans.iter().rev().skip_while(|o| o.is_none()).count());
645 ans
646 } else {
647 Default::default()
648 }
649 }
650
651 /// Returns the len of the binary tree.
652 ///
653 /// # Examples
654 ///
655 /// ```
656 /// use leetcode_test_utils::tree::T;
657 /// use leetcode_test_utils::btree;
658 ///
659 /// let tree = T(btree!(2, 4, null, 9));
660 /// assert_eq!(tree.len(), 3);
661 /// ```
662 pub fn len(&self) -> usize {
663 if let Some(ref rc) = self.0 {
664 let mut v = Vec::with_capacity(4);
665 let mut ret = 0_usize;
666 unsafe {
667 v.set_len(1);
668 *v.get_unchecked_mut(0) = rc.as_ptr() as *const TreeNode;
669 }
670 while !v.is_empty() {
671 let top = v.pop().unwrap();
672 ret += 1;
673 if let Some(rc) = unsafe { &(*top).right } {
674 v.push(rc.as_ptr());
675 }
676 if let Some(rc) = unsafe { &(*top).left } {
677 v.push(rc.as_ptr());
678 }
679 }
680 ret
681 } else {
682 0
683 }
684 }
685}
686
687// 2021/7/1; In progress
688// #[derive(Debug)]
689// pub struct ForestCmpResult {
690// requires_answer: Vec<String>,
691// not_answer: Vec<String>,
692// accepted: Vec<String>,
693// }
694//
695//
696// pub fn forest_eq_seq_insensitive(output: &[TreeHandle], answer: &str) -> ForestCmpResult {
697// unimplemented!()
698// }
699
700impl Display for T {
701 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
702 f.write_str(&self.to_leetcode_raw())
703 }
704}
705
706impl PartialEq for T {
707 fn eq(&self, other: &Self) -> bool {
708 // fixme: needs more efficient algorithm
709 self.pre_order().eq(&other.pre_order()) && self.in_order().eq(&other.in_order())
710 }
711}
712
713/// Construct a binary tree using the leetcode sequence format, excluding the square brackets.
714#[macro_export]
715macro_rules! btree {
716 () => { None };
717 ($($val: expr),+ $(,)?) => {
718 {
719 let values = vec![$(stringify!($val)),+].iter()
720 .map(|v|v.parse::<i32>().ok())
721 .collect::<Vec<Option<i32>>>();
722 leetcode_test_utils::tree::TreeBuilder::from_leetcode(values.as_slice())
723 }
724 };
725}
726
727/// Rapidly create a left child of the given node.
728///
729/// # Examples
730///
731/// ```
732/// use leetcode_test_utils::{new_left, btree};
733/// use leetcode_test_utils::tree::shortcuts::new_node;
734/// use leetcode_test_utils::tree::T;
735///
736/// let root = new_node(42);
737/// new_left!(root.as_ref().unwrap(), 10);
738/// assert_eq!(T(root), T(btree!(42, 10)));
739/// ```
740#[macro_export]
741macro_rules! new_left {
742 ($rc: expr, $val: expr) => {
743 $rc.borrow_mut().left = leetcode_test_utils::tree::shortcuts::new_node($val);
744 };
745}
746
747/// Rapidly create a right child of the given node.
748///
749/// # Examples
750///
751/// ```
752/// use leetcode_test_utils::{new_right, btree};
753/// use leetcode_test_utils::tree::shortcuts::new_node;
754/// use leetcode_test_utils::tree::T;
755///
756/// let root = new_node(42);
757/// new_right!(root.as_ref().unwrap(), 10);
758/// assert_eq!(T(root), T(btree!(42, null, 10)));
759/// ```
760#[macro_export]
761macro_rules! new_right {
762 ($rc: expr, $val: expr) => {
763 $rc.borrow_mut().right = leetcode_test_utils::tree::shortcuts::new_node($val);
764 };
765}
766
767/// Rapidly create left & right children of the given node.
768///
769/// # Examples
770///
771/// ```
772/// use leetcode_test_utils::{new_child, btree};
773/// use leetcode_test_utils::tree::shortcuts::new_node;
774/// use leetcode_test_utils::tree::T;
775///
776/// let root = new_node(42);
777///
778/// new_child!(root.as_ref().unwrap(), left, 2);
779/// assert_eq!(T(root.clone()), T(btree!(42, 2)));
780///
781/// new_child!(root.as_ref().unwrap(), l, 3);
782/// assert_eq!(T(root.clone()), T(btree!(42, 3)));
783///
784/// new_child!(root.as_ref().unwrap(), L, 4);
785/// assert_eq!(T(root.clone()), T(btree!(42, 4)));
786///
787/// new_child!(root.as_ref().unwrap(), right, 5);
788/// assert_eq!(T(root.clone()), T(btree!(42, 4, 5)));
789///
790/// new_child!(root.as_ref().unwrap(), r, 6);
791/// assert_eq!(T(root.clone()), T(btree!(42, 4, 6)));
792///
793/// new_child!(root.as_ref().unwrap(), R, 7);
794/// assert_eq!(T(root.clone()), T(btree!(42, 4, 7)));
795///
796/// new_child!(root.as_ref().unwrap(), [8, 9]);
797/// assert_eq!(T(root.clone()), T(btree!(42, 8, 9)));
798/// ```
799#[macro_export]
800macro_rules! new_child {
801 ($rc:expr, left, $val:expr) => {
802 leetcode_test_utils::new_left!($rc, $val);
803 };
804 ($rc:expr, l, $val:expr) => {
805 leetcode_test_utils::new_left!($rc, $val);
806 };
807 ($rc:expr, L, $val:expr) => {
808 leetcode_test_utils::new_left!($rc, $val);
809 };
810 ($rc:expr, right, $val:expr) => {
811 leetcode_test_utils::new_right!($rc, $val);
812 };
813 ($rc:expr, r, $val:expr) => {
814 leetcode_test_utils::new_right!($rc, $val);
815 };
816 ($rc:expr, R, $val:expr) => {
817 leetcode_test_utils::new_right!($rc, $val);
818 };
819 ($rc:expr, [$left:expr, $right:expr]) => {
820 leetcode_test_utils::new_left!($rc, $left);
821 leetcode_test_utils::new_right!($rc, $right);
822 };
823}