通过先序和中序数组生成后序数组

已知一棵二叉树所有节点值都不同，给定这个二叉树的先序和中序数组，不要重建整棵树，而是通过这两个数组直接生成正确的后序数组。

use std::collections::HashMap;

fn get_post_list(pre_list: Vec<i32>, in_list: Vec<i32>) -> Option<Vec<i32>> {
    if pre_list.is_empty() || in_list.is_empty() {
        return None;
    }

    let len = pre_list.len();
    assert_eq!(len, in_list.len());

    let mut post_list = vec![0; len];

    let in_record_map: HashMap<i32, i32> = in_list
        .iter()
        .enumerate()
        .map(|(i, &x)| (x, i as i32))
        .collect();

    process(
        &pre_list,
        0,
        len - 1,
        &in_list,
        0,
        len - 1,
        &mut post_list,
        len - 1,
        &in_record_map,
    );
    Some(post_list)
}

fn process(
    pre_list: &Vec<i32>,
    pre_start: usize,
    pre_end: usize,
    in_list: &Vec<i32>,
    in_start: usize,
    in_end: usize,
    post_list: &mut Vec<i32>,
    post_index: usize,
    in_record_map: &HashMap<i32, i32>,
) -> usize {
    if pre_start > pre_end {
        return post_index;
    }

    post_list[post_index] = pre_list[pre_start];

    if post_index == 0 {
        return post_index;
    }

    let post_index = post_index - 1;

    let split_index = in_record_map[&pre_list[pre_start]] as usize;

    let post_index = process(
        pre_list,
        split_index - in_start + pre_start + 1,
        pre_end,
        in_list,
        split_index + 1,
        in_end,
        post_list,
        post_index,
        in_record_map,
    );
    return process(
        pre_list,
        pre_start + 1,
        pre_start + split_index - in_start,
        in_list,
        in_start,
        split_index - 1,
        post_list,
        post_index,
        in_record_map,
    );
}

#[cfg(test)]

mod tests {
    use std::vec;

    #[test]
    fn it_works() {
        let pre_list = vec![1, 2, 4, 5, 3, 6, 7];
        let in_list = vec![4, 2, 5, 1, 6, 3, 7];

        let post_list = super::get_post_list(pre_list, in_list);

        assert!(post_list.is_some());
        assert_eq!(vec![4, 5, 2, 6, 7, 3, 1], post_list.unwrap());
    }
}

评论