面试经典150题 P105 从前序与中序遍历序列构造二叉树

---

时间轴

2025-10-26

init

---

题目：

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

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150

可以用递归实现，因为前序遍历的结果是：

root | root的左子树前序遍历结果 | root的右子树前序遍历结果

中序遍历结果是：

root左子树中序遍历结果 | root | root右子树的中序遍历结果

因此可以根据前序遍历找到root后，在中序遍历里可以计算到root左子树的大小，以及root右子树的大小，这样就知道了root左子树前序遍历结果以及root右子树前序遍历结果。用递归实现，边界条件是到达叶节点，pre_left == pre_right == root

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

struct Solution;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

impl Solution {
    fn build_tree_from_order(
        hash_map: &HashMap<i32, usize>,
        preorder: &Vec<i32>,
        inorder: &Vec<i32>,
        pre_left: usize,
        pre_right: usize,
        in_left: usize,
        in_right: usize,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if pre_left > pre_right {
            return None;
        }

        let root_val = preorder[pre_left];
        let root = Rc::new(RefCell::new(TreeNode::new(root_val)));

        let root_index_inorder = hash_map[&root_val];
        let left_tree_size = root_index_inorder - in_left;

        root.borrow_mut().left = Solution::build_tree_from_order(
            hash_map,
            preorder,
            inorder,
            pre_left + 1,
            pre_left + left_tree_size,
            in_left,
            root_index_inorder - 1,
        );

        root.borrow_mut().right = Solution::build_tree_from_order(
            hash_map,
            preorder,
            inorder,
            pre_left + left_tree_size + 1,
            pre_right,
            root_index_inorder + 1,
            in_right,
        );

        Some(root)
    }

    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut hash_map = HashMap::new();
        for (i, &val) in inorder.iter().enumerate() {
            hash_map.insert(val, i);
        }

        Solution::build_tree_from_order(
            &hash_map,
            &preorder,
            &inorder,
            0,
            preorder.len() - 1,
            0,
            inorder.len() - 1,
        )
    }
}

fn main() {
    let preorder = vec![3, 9, 20, 15, 7];
    let inorder = vec![9, 3, 15, 20, 7];

    let tree = Solution::build_tree(preorder, inorder);
    println!("{:?}", tree);
}