O(n) modularized & thread-safe Java Recursive Solution


  • 0
    L
    public class Solution {
        public TreeNode str2tree(String s) {
            if (s == null || s.length() == 0) {
                return null;
            }
            //Param start acts like a member variable, but thread-safe.
            return deserialize(s, new int[]{0} /*start*/);
        }
    
        private TreeNode deserialize(String s, int[] start /*in/out param*/) {
            if (start[0] >= s.length() || s.charAt(start[0]) == ')') {
                return null; //reach to end or left node is empty, e.g. 1()(2)
            }
            TreeNode root = getCurrentNode(s, start);
            root.left = getChildNode(s, start);
            root.right = getChildNode(s, start);
            return root;
        }
    
        private TreeNode getCurrentNode(String s, int[] start) {
            int end = start[0] + 1;
            while (end < s.length() && s.charAt(end) != '(' //middle nodes "val(...)" end with '('
                    && s.charAt(end) != ')') {  //leave node "(val)" end with ')'
                end++;
            }
            TreeNode root = new TreeNode(Integer.parseInt(s.substring(start[0], end)));
            start[0] = end; //reset start to the next point
            return root;
        }
    
        private TreeNode getChildNode(String s, int[] start) {
            TreeNode child = null;
            if (start[0] < s.length() && s.charAt(start[0]) == '(') {
                start[0]++; //skip '('
                child = deserialize(s, start);
                start[0]++; //skip ')'
            }
            return child;
        }
    }
    

Log in to reply
 

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