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, address scenarios where the tree is either empty or comprises a single node. In such instances, simply return null or the solitary node, respectively.

Iterate through the string, segregating the characters '(' and ')' from other elements. Employ the concept of preorder traversal, utilizing two stacks to maintain nodes and strings, respectively. Upon encountering a '(', push it onto the string stack. Conversely, when a ')' is encountered, continue popping from both stacks until the top element of the string stack is a '(', then remove the '(' from the string stack. When a numeric value is encountered, instantiate a new node with the number as its value and identify its parent node at the top of the node stack. Assign the new node as either the left or right child of the parent node, contingent upon the availability of the parent’s left child.

Ultimately, return the root node of the constructed 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 start == p: # or, 'if not root.left:'
                        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