Java Recursive Solution


  • 26
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) return null;
        int firstParen = s.indexOf("(");
        int val = firstParen == -1 ? Integer.parseInt(s) : Integer.parseInt(s.substring(0, firstParen));
        TreeNode cur = new TreeNode(val);
        if (firstParen == -1) return cur;
        int start = firstParen, leftParenCount = 0;
        for (int i=start;i<s.length();i++) {
            if (s.charAt(i) == '(') leftParenCount++;
            else if (s.charAt(i) == ')') leftParenCount--;
            if (leftParenCount == 0 && start == firstParen) {cur.left = str2tree(s.substring(start+1,i)); start = i+1;}
            else if (leftParenCount == 0) cur.right = str2tree(s.substring(start+1,i));
        }
        return cur;
    }
    

  • 0
    D

    Your idea is so clear and brilliant!!!


  • 0

    That's what I want, It's awesome!


  • 0
    Y

    Awesome. Very clear and easy to understand. Thank you for sharing.


  • 3

    Share my solution using recursion:
    For example, we have string 4(2(3)(1))(6(5)), to construct a binary tree, we can split the string to 3 parts:
    4
    (2(3)(1))
    (6(5))

    4 is the root val;
    (2(3)(1)) is left tree;
    (6(5)) is right tree;

    So the main part of code is how to split the string to 3 substrings:

        public TreeNode str2tree(String s) {
            if(s.length() == 0) return null;
            if(s.startsWith("(")){
               s = s.substring(1, s.length() - 1);
            }
            char[] sc = s.toCharArray();
            String[] strs = new String[3];
            int count = 0, start = 0;
            for(int i = 0; i < sc.length; i++){
                if(sc[i] == '('){
                    if(count == 0){
                        for(int j = 0; j < 3; j++){
                            if(strs[j] == null) {
                                strs[j] = s.substring(start,i);
                                start = i;
                                break;
                            }
                        }
                    }
                    count++;
                }
                if(sc[i] == ')') count--;
            }
    
            for(int j = 0; j < 3; j++){
                if(strs[j] == null) {
                    strs[j] = s.substring(start,s.length());
                    break;
                }
            }
    
            TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
            if(strs[1] != null) root.left = str2tree(strs[1]);
            if(strs[2] != null) root.right = str2tree(strs[2]);
            return root;
        }

  • 4
    D

    This is my recursion, beat 97%, just scan the string from left to right, every time we meet '(' , create left child node, then if we meet '(' again from the same parent node, we create right child node.

    If every time we meet ')', just return to parent node.

    public class Solution {
        
        int i = 0;
        
        public TreeNode str2tree(String s) 
        {
            if (s == null || s.length() == 0) { return null; }
            return helper(s.toCharArray());
        }
        
        private TreeNode helper(char[] s)
        {
            // done
            if (i == s.length) { return null; }
            
            // extract number
            StringBuilder num = new StringBuilder();
            while (i < s.length && s[i] != '(' && s[i] != ')') { num.append(s[i]); i++; }
            
            // create new node
            TreeNode n = null;
            if (num.length() != 0)
            {
                n = new TreeNode(Integer.parseInt(num.toString()));
            }
            // check parenthesis type
            if (i < s.length && s[i] == '(')
            {
                // create left child node
                i++;
                n.left = helper(s);
                i++;
                
                if (i < s.length && s[i] == '(')
                {
                    // create right child node
                    i++;
                    n.right = helper(s);
                    i++;
                }
            }
            // if meets ')', return to parent node
            return n;
        }
    }
    

  • 0
    H

    Use the queue in the recursion to avoid using the global item and no need to count the left and right parents.

        public TreeNode str2tree(String s) {
            if(s.length()==0) return null;
            Queue<Character> queue = new LinkedList<Character>();
            for(int i=0;i<s.length();i++)
            {    
                queue.offer(s.charAt(i));
            }
            return buildTree(queue);
        }
        
        public TreeNode buildTree(Queue<Character> queue) {
            if(queue.isEmpty()) return null;
            TreeNode node=new TreeNode(0);
            
            int value=0;
            int sign=1;
            while(!queue.isEmpty())
            {
                char top = queue.poll();
                if(top=='(')
                {
                    if(node.left==null) node.left=buildTree(queue);
                    else node.right=buildTree(queue);
                }
                else if(top==')')
                {
                    break;
                }
                else 
                {
                    if(top=='-')
                    {
                        sign=-1;
                        continue;
                    }
                    value=value*10+(top-'0');
                }
            }
            
            node.val=sign*value;
            return node;
        }
    

  • 0
    T

    @dongll very nice coding, I make it a bit more simpler:

    private int index = 0;    
    public TreeNode str2tree(String st) {
        if (index == st.length()) return null;                
        StringBuilder num = new StringBuilder(); //extract number
        while (index < st.length()) { 
            char c = st.charAt(index);
            if(c!='('&&c!=')') {
                num.append(c);
                index++; 
            } else break;
        }       
        TreeNode node = new TreeNode(Integer.parseInt(num.toString())); // create new node       
        if (index < st.length() && st.charAt(index) == '('){// check parenthesis type            
            index++;
            node.left = str2tree(st);// create left child node
            index++;            
            if (index < st.length() && st.charAt(index) == '('){                
                index++;
                node.right = str2tree(st);// create right child node
                index++;
            }
        }
        return node; // if meets ')', return to parent node
    }

  • 0
    B

    Once you get leftParenCount==0, you can break.


  • 0
    D
    This post is deleted!

  • 0
    M

    I am afraid this solution is not O(n) but at least O(nlgn) and at most O(n^2), while @dongll @tongzhou2 's solution is O(n);


  • 0
    F

    The string has 3 parts : root (left)(right). However, (left) and (right) might be empty.
    Actually, after we find the left part, we can break the loop and build right child using the rest string directly if the rest is not empty.
    Here is my version. More concise.

    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.