O(n) solution using stack


  • 0
    R

    The idea is:

    1. when '(' is encountered, we add it to stack.peek() node's children and push the previous number to stack
    2. when ')' is encountered, we do the same thing but pop it immediately.

    A lot of tricky boundary cases here to consider. But I guess the idea is right. Feel free to help optimize my code!

        public TreeNode str2tree(String s) {
            if(s==null || s.length()==0) return null;
            if(!s.contains("(")) return new TreeNode(Integer.valueOf(s));
            Stack<TreeNode> stack = new Stack<>();
            int num=0;
            int sign=1;
            for(int i=0; i<s.length(); i++){
                char c=s.charAt(i);
                if(c=='-') sign=-1;
                else if(c>='0' && c<='9') num=num*10+c-'0';
                else{
                    TreeNode t=new TreeNode(sign*num);
                    if(i>0 && s.charAt(i-1)!='(' & s.charAt(i-1)!=')' && !stack.isEmpty() && stack.peek().left==null){
                        stack.peek().left=t;    
                    }
                    else if(i>0 && s.charAt(i-1)!='(' & s.charAt(i-1)!=')' && !stack.isEmpty()){
                        stack.peek().right=t;
                    }
                    if(i>0 && s.charAt(i-1)!='(' & s.charAt(i-1)!=')') stack.push(t);
                    num=0;
                    sign=1;
                }
                
                if(c==')'){
                    stack.pop();
                    num=0;
                }
            }
            
            //while(stack.size()>1) stack.pop();
            return stack.pop();
        }
    

Log in to reply
 

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