Construct binary tree from string

String Stack Tree Depth-First Search Binary Tree

58.7% acceptance

Mar 31, 2026

1134

184

You need to construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure. You always start to construct the left child node of the parent first if it exists.

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 str2tree(s: String) -> Option<Rc<RefCell<TreeNode>>> {
    if s.is_empty() { return None; }
    let bytes = s.as_bytes();
    let mut idx = 0;
    Self::parse(bytes, &mut idx)
  }
  
  fn parse(s: &[u8], idx: &mut usize) -> Option<Rc<RefCell<TreeNode>>> {
    if *idx >= s.len() { return None; }
    let mut neg = false;
    if s[*idx] == b'-' {
      neg = true;
      *idx += 1;
    }
    let mut val = 0i32;
    while *idx < s.len() && s[*idx].is_ascii_digit() {
      val = val * 10 + (s[*idx] - b'0') as i32;
      *idx += 1;
    }
    if neg { val = -val; }
    let mut node = TreeNode::new(val);
    if *idx < s.len() && s[*idx] == b'(' {
      *idx += 1; // skip '('
      node.left = Self::parse(s, idx);
      *idx += 1; // skip ')'
    }
    if *idx < s.len() && s[*idx] == b'(' {
      *idx += 1; // skip '('
      node.right = Self::parse(s, idx);
      *idx += 1; // skip ')'
    }
    Some(Rc::new(RefCell::new(node)))
  }
}