Verbose Java Solution, Recursion


  • 13
    public class Solution {
        public TreeNode str2tree(String s) {
            // Base case
            if (s.length() == 0) return null;
            
            // Create root
            int i = 0, j = 0;
            while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;
            TreeNode root = new TreeNode(Integer.parseInt(s.substring(i, j)));
            
            // Left child
            if (j < s.length()) {
                i = j;
                int count = 1;
                while (j + 1 < s.length() && count != 0) {
                    j++;
                    if (s.charAt(j) == ')') count--;
                    if (s.charAt(j) == '(') count++;
                }
                root.left = str2tree(s.substring(i + 1, j));
            }
            
            j++;
            // Right child
            if (j < s.length()) {
                root.right = str2tree(s.substring(j + 1, s.length() - 1));
            }
            
            return root;
        }
    }
    

  • 0
    B

    @shawngao said in Verbose Java Solution, Recursion:

    while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;

    Thank you for the solution! I don`t understand above step. Why we need to check if s.charAt(j)=='-' ? Could you explain it?


  • 0

    @bigoffer4all There are negative integers. i.e. "1(-1)(2)".


  • 0
    Z

    It is difficult to get good performance using recursion. For C++, the run time could be up to O(n^2). I don't know Java though.


  • 0
    F
    class Solution {
        public TreeNode str2tree(String s) {
            if (s == null || s.length() == 0) {
                return null;
            }
            int firstLeft = s.indexOf('(');
            if (firstLeft == -1) {
                return new TreeNode(Integer.parseInt(s));
            }
            TreeNode root = new TreeNode(Integer.parseInt(s.substring(0, firstLeft)));
            int count = 0, i = firstLeft;
            while (i < s.length()) {
                if (s.charAt(i) == '(') {
                    count++;
                } else if (s.charAt(i) == ')') {
                    count--;
                }
                if (count == 0) {
                    root.left = str2tree(s.substring(firstLeft + 1, i));
                    break;
                }
                i++;
            }
            if (i != s.length() - 1) {
                root.right = str2tree(s.substring(i + 2, s.length() - 1));
            }
            return root;
        }
    }
    

Log in to reply
 

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