Solution Class Reference

Public Member Functions
TreeNode *	recoverFromPreorder (string traversal)

Detailed Description

Definition at line 15 of file main.cpp.

Member Function Documentation

recoverFromPreorder()

TreeNode * Solution::recoverFromPreorder ( string  traversal )

inline

Definition at line 18 of file main.cpp.

    {
        // (node, level)
        stack<pair<TreeNode*, int>> st;
        int i = 0;
 
        // interate through traversal string
        while (i < (int)traversal.size())
        {
            int level = 0;
 
            // count the dashes to determine current level
            while (i < (int)traversal.size() && traversal[i] == '-')
            {
                level++;
                i++;
            }
 
            int value = 0;
 
            // parse numeric value of current node
            while (i < (int)traversal.size() && isdigit(traversal[i]))
            {
                value = value * 10 + (traversal[i] - '0');
                i++;
            }
 
            // allocate new node
            TreeNode* node = new TreeNode(value);
            while (!st.empty() && st.top().second >= level)
                st.pop();
 
            // attach node to proper place using stack
            if (!st.empty())
            {
                if (!st.top().first->left)
                    st.top().first->left = node;
                else
                    st.top().first->right = node;
            }
 
            // push new node to the top of the stack
            st.push({node, level});
        }
 
        // drop all elements of the stack to uncover the root
        while ((int)st.size() > 1)
            st.pop();
        return st.top().first;
    }

References TreeNode::right.

Referenced by main().

---

The documentation for this class was generated from the following file:

• main.cpp