Struct TreeBuilder

pub struct TreeBuilder;

Associated function set for creating a binary tree.

Implementations

impl TreeBuilder

pub fn from_leetcode(values: &[Option<i32>]) -> TreeHandle

Build a binary tree using the parsed format in leetcode.

Returns the root of the binary tree specified in values.

Safety

You must make sure the values does be the valid input sequence of a binary tree, or the behaviour is undefined.

Examples

use leetcode_test_utils::tree::TreeBuilder;
use leetcode_test_utils::btree;

let t1 = TreeBuilder::from_leetcode(&[]);
assert_eq!(t1, btree!());

let t2 = TreeBuilder::from_leetcode(&[Some(1), None, Some(2)]);
assert_eq!(t2, btree!(1, null, 2));

pub fn from_leetcode_raw(s: &str) -> Result<TreeHandle, TreeError>

Build a binary tree using the raw format in leetcode(see Leetcode binary tree representation).

Returns the root of the binary tree specified in s, or Err indicating the parsing error.

Safety

You must make sure that the parsed pure sequence does be the valid binary tree, or the behaviour is undefined.

Examples

use leetcode_test_utils::tree::TreeBuilder;
use leetcode_test_utils::btree;
use leetcode_test_utils::tree::diagnosis::TreeError;

let t1 = TreeBuilder::from_leetcode_raw("[]");
assert_eq!(t1, Ok(btree!()));

let t2 = TreeBuilder::from_leetcode_raw("[1,null,2]");
assert_eq!(t2, Ok(btree!(1, null, 2)));

let t3 = TreeBuilder::from_leetcode_raw("(1,null,2)");
assert_eq!(t3.unwrap_err(), TreeError::LeetcodeFormatError);

let t4 = TreeBuilder::from_leetcode_raw("[1,none,2]");
assert_eq!(t4.unwrap_err(), TreeError::LeetcodeFormatError);

let t5 = TreeBuilder::from_leetcode_raw("[1,12345678901,3]"); // '12345678901' overflows i32
assert_eq!(t5.unwrap_err(), TreeError::LeetcodeFormatError);

pub fn from_twos( seq1_type: TraversalType, seq1: &[i32], seq2_type: TraversalType, seq2: &[i32], ) -> Result<TreeHandle, TreeError>

Build a binary tree with two specified orders and their sequences respectively.

A binary tree(no value occurs more than once) can be built with in-order and another order (say, pre-order, post-order or level order). This function builds the corresponding tree. If the two types are not legal, or any invariance is compromised, returns an Err.

This function is used when seq1_type or/and seq2_type is determined at runtime. If the types can be determined at compile time, use Self::from_pre_in, Self::from_post_in or Self::from_level_in instead.

Arguments

• seq1_type is the sequence type of seq1.
• seq2_type is the sequence type of seq2.

Examples

use leetcode_test_utils::tree::diagnosis::TraversalType;
use leetcode_test_utils::tree::{TreeBuilder, T};
use leetcode_test_utils::btree;

let arg = 1;
let type1 = match arg{   // determined at runtime
    1 => TraversalType::PreOrder,
    2 => TraversalType::PostOrder,
    _ => TraversalType::LevelOrder,
};
let type2 = TraversalType::InOrder;

let seq1 = vec![1, 4, 2, 8, 5, 7];  // also at runtime
let seq2 = vec![4, 2, 1, 5, 7, 8];

let tree = TreeBuilder::from_twos(type1, &seq1, type2, &seq2).unwrap();
let target = btree!(1, 4, 8, null, 2, 5, null, null, null, null, 7);
assert_eq!(tree, btree!(1, 4, 8, null, 2, 5, null, null, null, null, 7));

pub fn from_pre_in(pre_order: &[i32], in_order: &[i32]) -> TreeHandle

Build a tree using pre-order and in-order structures.

Returns the corresponding binary tree, or panics if some invariance is violated(a value occurs more than once, or pre_order.len() != in_order.len()).

Examples

use leetcode_test_utils::btree;
use leetcode_test_utils::tree::TreeBuilder;

let tree = TreeBuilder::from_pre_in(&[2, 1, 3], &[1, 2, 3]);
assert_eq!(tree, btree!(2, 1, 3));

pub fn from_post_in(post_order: &[i32], in_order: &[i32]) -> TreeHandle

Build a tree using post-order and in-order structures.

Returns the corresponding binary tree, or panics if some invariance is violated(a value occurs more than once, or post_order.len() != in_order.len()).

Examples

use leetcode_test_utils::btree;
use leetcode_test_utils::tree::TreeBuilder;

let tree = TreeBuilder::from_post_in(&[1, 3, 2], &[1, 2, 3]);
assert_eq!(tree, btree!(2, 1, 3));

pub fn from_level_in(level_order: &[i32], in_order: &[i32]) -> TreeHandle

Build a tree using level order and in-order structures.

Returns the corresponding binary tree, or panics if some invariance is violated(a value occurs more than once, or level_order.len() != in_order.len()).

Examples

use leetcode_test_utils::btree;
use leetcode_test_utils::tree::TreeBuilder;

let tree = TreeBuilder::from_level_in(&[1, 4, 8, 2, 5, 7], &[4, 2, 1, 5, 7, 8]);
assert_eq!(tree, btree!(1, 4, 8, null, 2, 5, null, null, null, null, 7));