One loop Java Solution


  • 0
    J
    public class Solution {
        public TreeNode str2tree(String s) {
            if(s==null || s.length()==0) return null;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            int num = 0; int sign = 1;
            char prevc = '/';TreeNode root =null;
            
            s+="()"; // incase input is a pure number
            
            for(int i=0;i<s.length();i++){
                char c = s.charAt(i);
        
                if(c=='-'){
                    sign = -1;
                }
                if(Character.isDigit(c)){
                    num=num*10+(c-'0');
                }
                if((c=='(' || c==')')&&Character.isDigit(prevc)){ //push number to stack when prev char is a digit and current char is a parenthesis
                    TreeNode node = new TreeNode(sign*num);
                    if(!stack.isEmpty()){
                        if(stack.peek().left==null)
                            stack.peek().left = node;
                        else if(stack.peek().right==null)
                            stack.peek().right = node;
                    }
                    stack.push(node);
                    sign = 1; num=0;
                }
                if(c==')'){
                    root = stack.pop();
                }
                prevc = c;
            }
            return root;
        }
    }
    
    

Log in to reply
 

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