Construct Binary Tree from String

• 

  Java Recursive Solution
  

  15
  29
  VOTES
  15
  Posts
  6655
  Views

  

  @dongll your answer is the best one so far thanks!

• 

  Java stack solution
  

  9
  16
  VOTES
  9
  Posts
  3878
  Views

  G

  Could the value be negative?

  There will only be (, ), - and 0 ~ 9 in the input string.

  The - is for negative number right?
  I guess the test cases does not contain such cases.

• 

  Verbose Java Solution, Recursion
  

  6
  13
  VOTES
  6
  Posts
  2346
  Views

  T

  Nice solution. May I know what's the time complexity for this code?

• 

  Python hack
  

  5
  10
  VOTES
  5
  Posts
  1154
  Views

  Z

  @StefanPochmann Yeah, totally understand, I think it is even harder to write a proper assertion program than actually solve this problem. So I think don't bother, just let it crash ;).

• 

  Python, Straightforward with Explanation
  

  1
  9
  VOTES
  1
  Posts
  696
  Views

  No one has replied

• 

  [C++] Clean Code
  

  2
  8
  VOTES
  2
  Posts
  870
  Views

  Z

  In build function, I think you should check whether i < s.size(). For test case "4", you may eventually check "s[1] == '(' ", which is invalid.

• 

  Short O(N) solution
  javascript linear short •

  2
  3
  VOTES
  2
  Posts
  873
  Views

  Z

  /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int i; public TreeNode str2tree(String s) { i = 0; return construct(s); } private TreeNode construct(String s) { // parse number StringBuilder numStr = new StringBuilder(); while (i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) { numStr.append(s.charAt(i)); i++; } if (numStr.length() == 0) return null; TreeNode root = new TreeNode(Integer.parseInt(numStr.toString())); // left subtree if (i < s.length() && s.charAt(i) == '(') { i++; // skip '(' root.left = construct(s); i++; // skip ')' } // right subtree if (i < s.length() && s.charAt(i) == '(') { i++; // skip '(' root.right = construct(s); i++; // skip ')' } return root; } }

  Java version based on your idea :-)

• T

  C++ stack solution
  

  1
  3
  VOTES
  1
  Posts
  159
  Views

  No one has replied

• T

  Java Recursive beats 90%, like solving Post-order DFS problems, with explanations.
  

  1
  3
  VOTES
  1
  Posts
  154
  Views

  No one has replied

• 

  Easy Understand and Clear Java Solution with explanation
  

  1
  2
  VOTES
  1
  Posts
  320
  Views

  No one has replied

• H

  C++ concise recursive solution
  

  2
  1
  VOTES
  2
  Posts
  384
  Views

  No one has replied

• X

  Is the input of "4()(3)" a valid case?
  

  4
  1
  VOTES
  4
  Posts
  416
  Views

  

  @xtermx In this problem, a null subtree is represented by empty string, not by a pair of () contains nothing. But good points, we should make it more clear in the description. Thanks!

• 

  Simple JavaScript using recursion
  javascript •

  1
  1
  VOTES
  1
  Posts
  109
  Views

  No one has replied

• X

  python one pass O(n) recursive
  

  1
  1
  VOTES
  1
  Posts
  168
  Views

  No one has replied

• T

  Java: top down recursive solution with O(N) time and O(1) space
  pre-order recursion o1 space •

  1
  1
  VOTES
  1
  Posts
  72
  Views

  No one has replied

• 

  Iterative Solution in Java O(n)
  

  1
  0
  VOTES
  1
  Posts
  201
  Views

  No one has replied

• H

  This topic is deleted!
  

  1
  0
  VOTES
  1
  Posts
  1
  Views

  No one has replied

• H

  Fast recursive java solution with single pointer
  

  1
  0
  VOTES
  1
  Posts
  120
  Views

  No one has replied

• G

  JAVA分治土办法--but effective
  

  1
  0
  VOTES
  1
  Posts
  139
  Views

  No one has replied

• T

  C++ stack 29ms
  

  1
  0
  VOTES
  1
  Posts
  77
  Views

  No one has replied