Java stack solution


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

  • 2

    Its reverse version of preorder traversal, so nice code and beautiful thought.


  • 0

    @Shadow-Fiend Thanks!!


  • 0
    Y
    This post is deleted!

  • 1
    Z

    Good solution! I have the same idea in C++.

    class Solution {
    public:
        TreeNode* str2tree(string s) {
            if (s == "") return nullptr;
            stack<TreeNode*> sk;
            int n = s.size(), i = 0;
            while(i < n && s[i] != '(' && s[i] != ')')
                i++;
            TreeNode *root = new TreeNode(stoi(s.substr(0, i)));
            sk.push(root);
            while (i < n) {
                if (s[i++] == ')') 
                    sk.pop();
                else {
                    int j = i;
                    while(i < n && s[i] != '(' && s[i] != ')')
                       i++;
                    TreeNode *p = new TreeNode(stoi(s.substr(j, i-j)));
                    if (sk.top()->left) 
                        sk.top()->right = p;
                    else
                        sk.top()->left = p;
                    sk.push(p);
                }
            }
            return root;
        }
    };
    

  • 0
    F

    @fallcreek said in Java stack solution:

    valueOf

    Awesome!
    I tried and cannot do it better.


  • -1
    S

    @fallcreek said in Java stack solution:

    stack.peek();

    this would not work for lets say 4(2()(3))


  • 0
    Q

    @soham6 There is no such situation. Pay attention to: An empty tree is represented by "" instead of "()".


  • 0
    G

    Could the value be negative?

    There will only be (, ), - and 0 ~ 9 in the input string.

    The - is for negative number right?
    I guess the test cases does not contain such cases.


Log in to reply
 

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