536. Construct Binary Tree from String

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.

 

Example 1:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Example 2:

Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Example 3:

Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

 

Constraints:

  • 0 <= s.length <= 3 * 104
  • s consists of digits, '(', ')', and '-' only.

Rust Solution

struct Solution;
use rustgym_util::*;
use std::iter::Peekable;
use std::vec::IntoIter;

enum Tok {
    Num(i32),
    Op(char),
}

use Tok::*;

struct TreeParser {
    it: Peekable<IntoIter<Tok>>,
}

impl TreeParser {
    fn new(s: String) -> Self {
        let mut tokens = vec![];
        let mut it = s.chars().peekable();
        while let Some(c) = it.next() {
            match c {
                '0'..='9' => {
                    let mut val = (c as u8 - b'0') as i32;
                    while let Some(&c) = it.peek() {
                        match c {
                            '0'..='9' => {
                                it.next();
                                val *= 10;
                                val += (c as u8 - b'0') as i32;
                            }
                            _ => {
                                break;
                            }
                        }
                    }
                    tokens.push(Num(val));
                }
                _ => {
                    tokens.push(Op(c));
                }
            }
        }
        let it = tokens.into_iter().peekable();
        TreeParser { it }
    }

    fn parse(&mut self) -> TreeLink {
        let sign = if self.eat('-') { -1 } else { 1 };
        if let Some(Num(val)) = self.it.next() {
            let mut left = None;
            let mut right = None;
            if self.eat('(') {
                left = self.parse();
                self.eat(')');
            }
            if self.eat('(') {
                right = self.parse();
                self.eat(')');
            }
            tree!(val * sign, left, right)
        } else {
            None
        }
    }

    fn eat(&mut self, c: char) -> bool {
        if let Some(&Op(t)) = self.it.peek() {
            if t == c {
                self.it.next();
                return true;
            }
        }
        false
    }
}

impl Solution {
    fn str2tree(s: String) -> TreeLink {
        TreeParser::new(s).parse()
    }
}

#[test]
fn test() {
    let s = "4(2(3)(1))(6(5))".to_string();
    let res = tree!(4, tree!(2, tree!(3), tree!(1)), tree!(6, tree!(5), None));
    assert_eq!(Solution::str2tree(s), res);
    let s = "-4(2(3)(1))(6(5))".to_string();
    let res = tree!(-4, tree!(2, tree!(3), tree!(1)), tree!(6, tree!(5), None));
    assert_eq!(Solution::str2tree(s), res);
}

Having problems with this solution? Click here to submit an issue on github.