Formatted question description: https://leetcode.ca/all/536.html

536. Construct Binary Tree from String

Level

Medium

Description

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:

Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5

Note:

  1. There will only be '(', ')', '-' and '0' ~ '9' in the input string.
  2. An empty tree is represented by "" instead of "()".

Solution

First consider the cases when the tree is empty or contains only one node. Simply return null or the single node in such cases.

Loop over the string and split the terms '(' and ')' with other terms. Use the idea of preorder traversal, where two stacks are used to store nodes and strings. If a '(' is met, then push the '(' into the string stack. If a ')' is met, then pop both stacks until the string stack’s top element is '(', and pop '(' from the string stack. If a number is met, create a new node with the number as the value, and find its parent at the top of the node stack. Set the current node to be its parent’s left node or right node depending on whether the parent’s left node is null.

Finally, return the root of the tree.

public class Construct_Binary_Tree_from_String {

    /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
    class Solution {

        private int start = 0;

        public TreeNode str2tree(String s) {
            if (s == null || s.length() == 0) {
                return null;
            }

            return str2treeHelper(s);
        }

        private TreeNode str2treeHelper(String s) {
            if (start >= s.length()) {
                return null;
            }

            // parse int
            //
            boolean neg = false;
            if (s.charAt(start) == '-') {
                neg = true;
                start++;
            }
            int num = 0;
            while (start < s.length() && Character.isDigit(s.charAt(start))) {
                int digit = Character.getNumericValue(s.charAt(start));
                num = num * 10 + digit;
                start++;
            }

            if (neg) {
                num = -num;
            }

            TreeNode root = new TreeNode(num);

            if (start >= s.length()) {
                return root;
            }

            // go to left child
            //
            if (start < s.length() && s.charAt(start) == '(') {
                start++;
                root.left = str2treeHelper(s);
            }

            if (start < s.length() && s.charAt(start) == ')') {
                start++;
                return root;
            }

            // go to the right child
            //
            if (start < s.length() && s.charAt(start) == '(') {
                start++;
                root.right = str2treeHelper(s);
            }

            if (start < s.length() && s.charAt(start) == ')') {
                start++;
                return root;
            }

            return root;
        }
    }
}

All Problems

All Solutions