Java O(n) Solution


  • 0
    M
        public TreeNode str2tree(String s) {
            if (s == null) return null;
            Queue<Character> q = new LinkedList<>();
            for (char c : s.toCharArray()) q.offer(c);
            return build(q);
        }
        private TreeNode build(Queue<Character> q) {
            if (q.isEmpty()) return null;
            StringBuilder val = new StringBuilder();
            while (!q.isEmpty() && (q.peek() == '-' || Character.isDigit(q.peek()))) {
                val.append(q.poll());
            }
            if (val.length() == 0) return null;
            TreeNode root = new TreeNode(Integer.parseInt(val.toString()));
            if (!q.isEmpty() && q.peek() == '(') {
                q.poll();
                root.left = build(q);
                q.poll();
                if (!q.isEmpty() && q.peek() == '(') {
                    q.poll();
                    root.right = build(q);
                    q.poll();
                }
            }
            return root;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.