Welcome to Subscribe On Youtube
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) }