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]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcstr2tree(sstring)*TreeNode{vardfsfunc(sstring)*TreeNodedfs=func(sstring)*TreeNode{ifs==""{returnnil}p:=strings.IndexAny(s,"(")ifp==-1{v,_:=strconv.Atoi(s)return&TreeNode{Val:v}}v,_:=strconv.Atoi(s[:p])root:=&TreeNode{Val:v}start:=pcnt:=0fori:=p;i<len(s);i++{ifs[i]=='('{cnt++}elseifs[i]==')'{cnt--}ifcnt==0{ifp==start{root.Left=dfs(s[start+1:i])start=i+1}else{root.Right=dfs(s[start+1:i])}}}returnroot}returndfs(s)}