Using Queue recursive solving like 449


  • 0
    W

    public class Solution {
    //4(2(3)(1))(6(5)) ==> 4(2(3(# (1(#(# (6(5(#(#
    // ==> 4-2-3-#-#1-#-#6-5-#-#-#
    // )( -->(#(# ))(-->(#(# last replace )) --> (#(#(#
    4
    /
    2 6
    / \ /
    3 1 5

    //4(2(3)(1))(6(5)) ==> 4(2(3(#  (1(#(#  (6(5(#(#
    //                       ==> 4-2-3-#-#-1-#-#-6-5-#-#-#
    // )( -->(#(#(    and ))(-->(#(#(    and last replace )) --> (#(#(# or ) -->(#(#
    	   //before=4(2(3)(1))(6(5))
          // after=4(2(3(#(#(1(#(#(6(5(#(#(#
    
    public TreeNode str2tree(String s) {
        if(s==null || s.length() <=0) return null;
        s = s.replaceAll("\\)\\)\\(", "(#(#(");
        s = s.replaceAll("\\)\\(", "(#(#(");
        s = s.replaceAll("\\)\\)", "(#(#(#");
        s = s.replaceAll("\\)", "(#(#");
        Queue<String> q = new LinkedList<>();
        String[] str = s.split("\\(");
        for(String one : str) {
            q.offer(one);
        }
        
        return help(q);
    }
    
    //the replacement is still not correct. can't pass 4(2(3))(6(5)(7)), anyone who can correct for me?
    public TreeNode help(Queue<String> q) {
        if(q.isEmpty()) return null;
        String top = q.poll();
        if(top.equals("#")) return null;
        int num = Integer.parseInt(top);
        TreeNode root = new TreeNode(num);
        root.left = help(q);
        root.right = help(q);
        return root;
    }
    

    }


Log in to reply
 

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