从前序与中序遍历序列构造二叉树

private Map<Integer, Integer> pos = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        pos.put(inorder[i], i); // 值 -> 中序下标
    }
    return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode build(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) {
    if (preLeft > preRight) {
        return null;
    }
    int mid = pos.get(preorder[preLeft]); // 根在中序中的位置
    int leftSize = mid - inLeft;
    TreeNode root = new TreeNode(preorder[preLeft]);
    root.left = build(preorder, preLeft + 1, preLeft + leftSize, inLeft, mid - 1);
    root.right = build(preorder, preLeft + leftSize + 1, preRight, mid + 1, inRight);
    return root;
}

def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    pos = {v: i for i, v in enumerate(inorder)}  # 值 -> 中序下标

    def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> Optional[TreeNode]:
        if pre_left > pre_right:
            return None
        mid = pos[preorder[pre_left]]  # 根在中序中的位置
        left_size = mid - in_left
        root = TreeNode(preorder[pre_left])
        root.left = build(pre_left + 1, pre_left + left_size, in_left, mid - 1)
        root.right = build(pre_left + left_size + 1, pre_right, mid + 1, in_right)
        return root

    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

func buildTree(preorder []int, inorder []int) *TreeNode {
    pos := make(map[int]int, len(inorder)) // 值 -> 中序下标
    for i, v := range inorder {
        pos[v] = i
    }
    var build func(preLeft, preRight, inLeft, inRight int) *TreeNode
    build = func(preLeft, preRight, inLeft, inRight int) *TreeNode {
        if preLeft > preRight {
            return nil
        }
        mid := pos[preorder[preLeft]] // 根在中序中的位置
        leftSize := mid - inLeft
        root := &TreeNode{Val: preorder[preLeft]}
        root.Left = build(preLeft+1, preLeft+leftSize, inLeft, mid-1)
        root.Right = build(preLeft+leftSize+1, preRight, mid+1, inRight)
        return root
    }
    return build(0, len(preorder)-1, 0, len(inorder)-1)
}

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    // 值 -> 中序下标
    let pos: HashMap<i32, usize> = inorder.iter().enumerate().map(|(i, &v)| (v, i)).collect();

    // 用 isize 区间，空区间时右端点会比左端点小 1
    fn build(
        preorder: &[i32],
        pos: &HashMap<i32, usize>,
        pre_left: isize, pre_right: isize,
        in_left: isize, in_right: isize,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if pre_left > pre_right {
            return None;
        }
        let root_val = preorder[pre_left as usize];
        let mid = pos[&root_val] as isize; // 根在中序中的位置
        let left_size = mid - in_left;
        let root = Rc::new(RefCell::new(TreeNode::new(root_val)));
        root.borrow_mut().left =
            build(preorder, pos, pre_left + 1, pre_left + left_size, in_left, mid - 1);
        root.borrow_mut().right =
            build(preorder, pos, pre_left + left_size + 1, pre_right, mid + 1, in_right);
        Some(root)
    }

    let n = preorder.len() as isize;
    build(&preorder, &pos, 0, n - 1, 0, n - 1)
}