Fast recursive java solution with single pointer


  • 0
    H

    invariant: 'start' always points to the first char of the next node to parse.

        public class Solution {
            private int start;
    
            public TreeNode str2tree(String s) {
                start = 0;
                return build(s);
            }
    
            private boolean notSpecial(char ch) {
                return ch == '-' || ch >= '0' && ch <= '9';
            }
    
            private TreeNode build(String s) {
                if (start == s.length())
                    return null;
    
                int numIndex = start;
                while (start < s.length() && notSpecial(s.charAt(start))) {
                    start++;
                }
                TreeNode node = new TreeNode(Integer.parseInt(s.substring(numIndex, start)));
                if (start == s.length() || s.charAt(start) == ')') {
                    return node;
                }
                //parse children
                assert s.charAt(start) == '(';
                start++;
                node.left = build(s);
                start++;
                if (start < s.length() && s.charAt(start) == '(') {
                    start++;
                    node.right = build(s);
                    start++;
                }
    
                return node;
            }
        }
    

Log in to reply
 

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