Construct binary tree from inorder and postorder traversal

Array Hash Table Divide and Conquer Tree Binary Tree

68.1% acceptance

Feb 27, 2026

8665

157

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[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
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn build_tree_inorder_postorder(inorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    if postorder.is_empty() {
      return None;
    }
    
    fn build(inorder: &[i32], postorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
      if postorder.is_empty() {
        return None;
      }
      
      let root_val = postorder[postorder.len() - 1];
      let root_idx = inorder.iter().position(|&x| x == root_val).unwrap();
      
      let left = build(&inorder[..root_idx], &postorder[..root_idx]);
      let right = build(&inorder[root_idx + 1..], &postorder[root_idx..postorder.len() - 1]);
      
      Some(Rc::new(RefCell::new(TreeNode {
        val: root_val,
        left,
        right,
      })))
    }
    
    build(&inorder, &postorder)
  }
}