Java Recursive Solution without copying string


  • 0
    G

    My solution is a little bit "complex", but it doesn't copying string(using substring etc).

    public TreeNode str2tree(String s) {
        return build(s, new int[] {0});
    }
    private TreeNode build(String s, int[] start) {
        TreeNode root = null;
        boolean isNegative = false;
        while (start[0] < s.length()) {
            char c = s.charAt(start[0]);
            if (Character.isDigit(c) || c == '-') {
                if (c == '-') {
                    isNegative = true;
                } else {
                    if (root == null) {
                        root = new TreeNode(isNegative ? (c - '0') * -1 : (c - '0'));
                    } else {
                        root.val = root.val * 10 + (isNegative ? (c - '0') * -1 : (c - '0'));
                    }
                }
                start[0]++;
            } else {
                if (c == '(') {
                    start[0]++;
                    root.left = build(s, start);
                    if (start[0] < s.length() && s.charAt(start[0]) == '(') {
                        start[0]++;
                        root.right = build(s, start);
                    }
                } else if (c == ')') {
                    start[0]++;
                    return root;
                }
            }
        }
        return root;
    }
    

    The idea is simple check every number and when encounter a "(", it will recursively calculate the left sub tree and also will try to calculate the right sub tree.


Log in to reply
 

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