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}