LeetCode 1028. 从先序遍历还原二叉树（栈）

示例 1：
输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]

示例 2：
输入："1-2--3---4-5--6---7"
输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：
输入："1-401--349---90--88"
输出：[1,401,null,349,88,90]

class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        int depth = 0, i = 0, val = 0;
        stack<pair<TreeNode*,int>> stk;
        TreeNode *root, *cur;
        val = getVal(S,i);
        root = new TreeNode(val);
        stk.push(make_pair(root,0));
        while(i < S.size())
        {
        	depth = getDep(S,i);
        	val = getVal(S,i);
        	cur = new TreeNode(val);
        	while(stk.top().second >= depth)
        		stk.pop();
        	if(stk.top().first->left)
        		stk.top().first->right = cur;
        	else
        		stk.top().first->left = cur;
        	stk.push(make_pair(cur,depth));
        }
        return root;
    }

    int getVal(string &S, int &i)//获取数字
    {
    	int val = 0;
    	while(i < S.size() && isdigit(S[i]))
    		val = val*10+S[i++]-'0';
    	return val;
    }
    int getDep(string &S, int &i)//获取深度
    {
    	int depth = 0;
    	while(S[i] == '-')
    	{
    		depth++;
    		i++;
    	}
    	return depth;
    }
};