105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Rust Solution

struct Solution;
use rustgym_util::*;

impl Solution {
    fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> TreeLink {
        let n = preorder.len();
        Self::build(&preorder[0..n], &inorder[0..n])
    }

    fn build(preorder: &[i32], inorder: &[i32]) -> TreeLink {
        let n = preorder.len();
        if n == 0 {
            None
        } else {
            let val = preorder[0];
            let i = inorder.iter().position(|&x| x == val).unwrap();
            tree!(
                val,
                Self::build(&preorder[1..=i], &inorder[0..i]),
                Self::build(&preorder[i + 1..], &inorder[i + 1..])
            )
        }
    }
}

#[test]
fn test() {
    let preorder = vec![3, 9, 20, 15, 7];
    let inorder = vec![9, 3, 15, 20, 7];
    let res = tree!(3, tree!(9), tree!(20, tree!(15), tree!(7)));
    assert_eq!(Solution::build_tree(preorder, inorder), res);
}

Having problems with this solution? Click here to submit an issue on github.