536. Construct Binary Tree from String

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example 1:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Example 2:

Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Example 3:

Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

Constraints:

• 0 <= s.length <= 3 * 10^4
• s consists of digits, ‘(‘, ‘)’, and ‘-‘ only.

Code

106

class Solution {
    public TreeNode str2tree(String s) {
        if (s.length() == 0) return null;
        
        int rootEnd = s.indexOf("(");
        
        if(rootEnd == -1){
            return new TreeNode(Integer.parseInt(s));
        }
        
        int rootVal = Integer.parseInt(s.substring(0, rootEnd)); 
        
        TreeNode curr = new TreeNode(rootVal);
        
        // 第一个左括号位置
        int start = rootEnd;
        int leftParenCount = 0;
        
        for (int i = start; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c == '(') {
                leftParenCount++;
            }else if (c == ')') {
                leftParenCount--;
            }
            
            if (leftParenCount == 0) {
                if(start == rootEnd) {
                    curr.left = str2tree(s.substring(start + 1, i)); 
                    start = i + 1;                  
                } else {
                    curr.right = str2tree(s.substring(start + 1, i));
                }
            }
        }
        
        return curr;
    }
}

class Solution {
    public TreeNode str2tree(String s) {
        if(s.length() == 0) return null;
        
        Stack<TreeNode> stack = new Stack<>();
        
        for(int i = 0, j = i; i < s.length(); i++, j = i){
            char c = s.charAt(i);
            
            if(c == '(') continue;
                
            if(c == ')') {
                stack.pop();
            } else if(Character.isDigit(c) || c == '-'){
                while(i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    i++;
                }
                
                TreeNode curr = new TreeNode(Integer.valueOf(s.substring(j, i + 1)));
                
                if(!stack.isEmpty()){
                    TreeNode parent = stack.peek();
                    if(parent.left != null) {
                        parent.right = curr;
                    } else {
                        parent.left = curr;
                    }
                }
                
                stack.push(curr);
            }
        }
        
        return stack.peek();
    }
}