Java Stack


  • 0
    V
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode str2tree(String s) {
            Stack<TreeNode> stk = new Stack<>();
            int sign = 1;
            char[] A = s.toCharArray();
            for (int i = 0; i < A.length; i++) {
                if (A[i] == '-') {
                    sign = -1;
                } else {
                    if (isDigit(A[i])) {
                        int start = i;
                        while(i < A.length && isDigit(A[i])) i++;
                        Integer val = Integer.parseInt(s.substring(start, i));
                        TreeNode root = new TreeNode(sign * val);
                        stk.push(root);
                        i--;
                    } else if (A[i] == ')') {
                        TreeNode child = stk.pop();
                        TreeNode root = stk.pop();
                        if (root.left == null) root.left = child;
                        else root.right = child;
                        stk.push(root);
                    }
                    sign = 1;
                }
            }
            
            return (stk.isEmpty()) ? null : stk.pop();
        }
        
        boolean isDigit(char c) {
            return c <= '9' && c >= '0';
        }
    }
    

Log in to reply
 

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