[leetcode] 1028. Recover a Tree From Preorder Traversal : https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

Recover a Tree From Preorder Traversal.cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // {val, depth}
	pair<int, int> getValAndDepth(string& s) {
		if (s.size() == 0)
			return { -1, -1 };
		int ind = 0;
		int val = 0;
		int depth = 0;
		for (; ind<s.size(); ind++) {
			if (s[ind] == '-') {
				if (val > 0) {
					ind--;
					break;
				}
				else depth++;
			}
			else {
				val *= 10;
				val += s[ind] - '0';
			}
		}
		s.erase(0, ind + 1);
		return { val, depth };
	}


	TreeNode* recoverFromPreorder(string S) {
		int nowDepth = -1;
		TreeNode* root = NULL;
		TreeNode* nowNode = NULL;

		pair<int, int> valAndDepth = getValAndDepth(S);
		int val = valAndDepth.first;
		int depth = valAndDepth.second;

		stack<TreeNode*> parentQ;

		while (depth != -1) {
			if (nowDepth + 1 == depth || nowNode == NULL) { // when parent
				TreeNode* newNode = new TreeNode(val);
				if (nowNode == NULL) {
					root = newNode;
				}else if (nowNode->left == NULL) {
					nowNode->left = newNode;
				}
				else {
					nowNode->right = newNode;
				}
				parentQ.push(nowNode);
				nowNode = newNode;
				nowDepth = depth;

				valAndDepth = getValAndDepth(S);
				val = valAndDepth.first;
				depth = valAndDepth.second;
				continue;
			}

			if (nowDepth < depth) {// should go right
				nowNode = nowNode->right;
				parentQ.push(nowNode);
				nowDepth++;
			}
			else {  // should up
				nowNode = parentQ.top();
				parentQ.pop();
				nowDepth--;
			}
		}
		return root;
	}
};