面试经典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;

        if left_tree_size > 0 {
            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,
            );
        }

        if in_right - root_index_inorder > 0 {
            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);
}

leetcode hot 100 rewrite

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode()
                : val(0)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x, TreeNode *left, TreeNode *right)
                : val(x)
                , left(left)
                , right(right)
        {
        }
};

#include <vector>
#include <unordered_map>

using std::vector;
using std::unordered_map;

class Solution {
    private:
        unordered_map<int, int> val2index;
        TreeNode *__buildTree(vector<int> &preorder, vector<int> &inorder, int pre_start,
                              int pre_end, int in_start, int in_end)
        {
                if (pre_start > pre_end || in_start > in_end)
                        return nullptr;

                TreeNode *root;
                int index, nr_left;

                root = new TreeNode;
                root->val = preorder[pre_start];

                index = val2index[root->val];
                nr_left = index - in_start;

                root->left = __buildTree(preorder, inorder, pre_start + 1, pre_start + nr_left,
                                         in_start, index - 1);

                root->right = __buildTree(preorder, inorder, pre_start + nr_left + 1, pre_end,
                                          index + 1, in_end);

                return root;
        }

    public:
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
        {
                int i, n = inorder.size();

                for (i = 0; i < n; i++)
                        val2index[inorder[i]] = i;

                return __buildTree(preorder, inorder, 0, preorder.size() - 1, 0,
                                   inorder.size() - 1);
        }
};