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:

There will only be '(', ')', '-' and '0' ~ '9' in the input string.
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;
        }
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode str2tree(String s) {
        return dfs(s);
    }

    private TreeNode dfs(String s) {
        if ("".equals(s)) {
            return null;
        }
        int p = s.indexOf("(");
        if (p == -1) {
            return new TreeNode(Integer.parseInt(s));
        }
        TreeNode root = new TreeNode(Integer.parseInt(s.substring(0, p)));
        int start = p;
        int cnt = 0;
        for (int i = p; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++cnt;
            } else if (s.charAt(i) == ')') {
                --cnt;
            }
            if (cnt == 0) {
                if (start == p) {
                    root.left = dfs(s.substring(start + 1, i));
                    start = i + 1;
                } else {
                    root.right = dfs(s.substring(start + 1, i));
                }
            }
        }
        return root;
    }
}

/**
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* str2tree(string s) {
        return dfs(s);
    }

    TreeNode* dfs(string s) {
        if (s == "") return nullptr;
        int p = s.find("(");
        if (p == s.npos) return new TreeNode(stoi(s));
        TreeNode* root = new TreeNode(stoi(s.substr(0, p)));
        int start = p;
        int cnt = 0;
        for (int i = p; i < s.size(); ++i) {
            if (s[i] == '(')
                ++cnt;
            else if (s[i] == ')')
                --cnt;
            if (cnt == 0) {
                if (start == p) {
                    root->left = dfs(s.substr(start + 1, i - start - 1));
                    start = i + 1;
                } else
                    root->right = dfs(s.substr(start + 1, i - start - 1));
            }
        }
        return root;
    }
};

'''
>>> a = "a(b(c("
>>> a.find("(")
1

>>> a = "-1"
>>> int(a)
-1
'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def str2tree(self, s: str) -> TreeNode:
        def dfs(s):
            if not s:
                return None
            p = s.find('(')
            if p == -1:
                return TreeNode(int(s))
            root = TreeNode(int(s[:p]))
            start = p
            cnt = 0
            for i in range(p, len(s)):
                if s[i] == '(':
                    cnt += 1
                elif s[i] == ')':
                    cnt -= 1
                if cnt == 0:
                    if not root.left: # or, 'if start == p:'
                        root.left = dfs(s[start + 1 : i])
                        start = i + 1
                    else:
                        root.right = dfs(s[start + 1 : i])
            return root

        return dfs(s)

##########

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def str2tree(self, s):
    """
    :type s: str
    :rtype: TreeNode
    """
    if s:
      cnt = start = 0
      root = None
      for i, c in enumerate(s):
        if c == "(":
          if not root and cnt == 0:
            root = TreeNode(s[:i])
          cnt += 1
          if cnt == 1:
            start = i + 1
        if c == ")":
          cnt -= 1
          if cnt == 0:
            if not root.left:
              root.left = self.str2tree(s[start:i])
            else:
              root.right = self.str2tree(s[start:i])
      return root if root else TreeNode(s)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func str2tree(s string) *TreeNode {
	var dfs func(s string) *TreeNode
	dfs = func(s string) *TreeNode {
		if s == "" {
			return nil
		}
		p := strings.IndexAny(s, "(")
		if p == -1 {
			v, _ := strconv.Atoi(s)
			return &TreeNode{Val: v}
		}
		v, _ := strconv.Atoi(s[:p])
		root := &TreeNode{Val: v}
		start := p
		cnt := 0
		for i := p; i < len(s); i++ {
			if s[i] == '(' {
				cnt++
			} else if s[i] == ')' {
				cnt--
			}
			if cnt == 0 {
				if p == start {
					root.Left = dfs(s[start+1 : i])
					start = i + 1
				} else {
					root.Right = dfs(s[start+1 : i])
				}
			}
		}
		return root
	}
	return dfs(s)
}

536 - Construct Binary Tree from String

536. Construct Binary Tree from String

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

536. Construct Binary Tree from String

Level

Description

Solution

All Problems

All Solutions