Interview Classic 150 Questions P105 Construct Binary Tree from Preorder and Inorder Traversal

---

Timeline

Timeline

2025-10-26

init

Construct Binary Tree from Preorder and Inorder Traversal

---

Problem:

P105 Construct Binary Tree from Preorder and Inorder Traversal

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

It can be implemented recursively, because the result of preorder traversal is:

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

The result of inorder traversal is:

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

Therefore, after finding the root from the preorder traversal, we can calculate the size of the root’s left subtree and the size of the root’s right subtree in the inorder traversal. This way, we know the preorder traversal results of the root’s left subtree and the root’s right subtree. Implement it recursively, with the boundary condition being reaching a leaf node, 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);
        }
};