BiruLyu
7/10/2017 - 8:14 PM

536. Construct Binary Tree from String(Stack).java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode str2tree(String s) {
        // Base case
        if (s.length() == 0) return null;
        
        // Create root
        int i = 0, j = 0;
        while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;
        TreeNode root = new TreeNode(Integer.valueOf(s.substring(i, j)));
        
        // Left child
        if (j < s.length()) {
            i = j;
            int count = 1;
            while (j + 1 < s.length() && count != 0) {
                j++;
                if (s.charAt(j) == ')') count--;
                if (s.charAt(j) == '(') count++;
            }
            root.left = str2tree(s.substring(i + 1, j));
        }
        
        j++;
        // Right child
        if (j < s.length()) {
            root.right = str2tree(s.substring(j + 1, s.length() - 1));
        }
        
        return root;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int index;
    public TreeNode str2tree(String s) {
        if(s.length() == 0) return null;
        char[] c = s.toCharArray();
        index = 0;
        return helper(c);
    }
    
    public TreeNode helper(char[] c){
        if(index >= c.length) return null;
        int num = 0; 
        boolean sign = true;
        if(c[index] == '-') 
        { 
            sign = false; 
            index++;
        }
        while( index < c.length && c[index] >= '0' && c[index] <= '9') {
            num = num * 10 + c[index] - '0';
            index++;
        }
        if(!sign) num = -num;
        TreeNode res = new TreeNode(num);
        if(index < c.length && c[index] == '('){
            index++; 
            res.left = helper(c);
        }
        if(index < c.length && c[index] == '('){
            index++; 
            res.right = helper(c);
        }
        if(index < c.length && c[index] == ')') 
            index++;
        return res;
    } 
    
    
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public TreeNode str2tree(String s) {
        if(s.length()==0) return null;
        char[] c = s.toCharArray();
        int index = 0;
        int sign = 1;
        if(c[index]=='-') {sign=-1; index++;}
        int num = 0;
        while(index<c.length && c[index]>='0' && c[index]<='9'){
            num = num * 10 + c[index]-'0';
            index++;
        }
        num = num*sign; sign = 1;
        TreeNode root = new TreeNode(num);
        Stack<TreeNode> st = new Stack();
        st.push(root);
        while(index<c.length)
        {
            if(c[index]=='(') 
            {
                index++;
                if(c[index]=='-') {sign=-1; index++;}
                num = 0;
                while(index<c.length && c[index]>='0' && c[index]<='9'){
                    num = num * 10 + c[index]-'0';
                    index++;
                }
                num = num*sign; sign = 1;
                TreeNode r = st.peek();
                TreeNode child = new TreeNode(num);
                if(r.left==null) r.left = child;
                else r.right = child;
                st.push(child);
            }
            if(c[index]==')') {st.pop(); index++;}
        }
        return root;
    }
    
}