leetcode 1028. Recover a Tree From Preorder Traversal
题意：给一个二叉树的深度优先的前序遍历，重建一颗二叉树。
输入："1-2--3--4-5--6--7"
输出：[1,2,5,3,4,6,7]
思路：主要的难点是5的父节点是1，这里考虑用stack保存，当前节点以及节点所在的层数。
通过更新栈顶元素，来找当前点的父节点。
代码：
class Solution {
public:TreeNode* recoverFromPreorder(string S) {int num = 0;int num_ = 0;TreeNode* root;stack<pair<TreeNode*, int>> s;for (int i = 0; i<S.size(); i++){if (S[i] != '-'){num = num * 10 + S[i] - '0';if (i == S.size() - 1 || S[i+1] == '-'){//cout<<num_<<'-'<<num<<endl;if (s.empty()){TreeNode* now = new TreeNode(num);root = now;s.push(make_pair(now, 0));}else{while (!s.empty()){if (s.top().second != num_ - 1)s.pop();elsebreak;}TreeNode* father = s.top().first;TreeNode* now = new TreeNode(num);s.push(make_pair(now, num_));if (father->left == nullptr)father->left = now;elsefather->right = now;}num = 0;num_ = 0;}}else if (S[i] == '-'){num_++;}}return root;}
};