我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，还原树并返回其根节点 root。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal
示例 1：
输入："1-2--3--4-5--6--7" 输出：[1,2,5,3,4,6,7]
执行用时 :28 ms, 在所有 C++ 提交中击败了82.24%的用户
内存消耗 :20.3 MB, 在所有 C++ 提交中击败了100.00%的用户
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
typedef struct deTree {TreeNode *node;int depth;
}DeTree;
class Solution {
public:TreeNode* recoverFromPreorder(string S) {vector<DeTree> deptreearr;int num = 0;int count = 0;int len = S.length();for(int i = 0;i<len;i++){while(i<len && S[i]=='-'){count++;i++;}while(i<len && S[i]!='-'){num = num*10 + S[i]-'0';i++;}DeTree t;t.node = new TreeNode(num);t.depth = count;deptreearr.push_back(t);num = 0;count = 1;}TreeNode *root = deptreearr[0].node;for(int i = 1;i<deptreearr.size();i++){if(deptreearr[i].depth>deptreearr[i-1].depth){deptreearr[i-1].node->left = deptreearr[i].node;}else if(deptreearr[i].depth==deptreearr[i-1].depth){//为什么我不判断i-2是否溢出范围，因为按照题目要求给出的用例就一定不会超出范围//这里i-1的父节点一定是i-2deptreearr[i-2].node->right = deptreearr[i].node;}else if(deptreearr[i].depth<deptreearr[i-1].depth){//当前深度小于前一个节点的深度，则这个节点一定是右节点，//因为如果节点只有一个子节点，那么保证该子节点为左子节点//所以往前面遍历找到和它的深度相等的节点，就可以找到他们的父节点for(int j = i-2;j>=0;j--){if(deptreearr[i].depth>deptreearr[j].depth){deptreearr[j].node->right = deptreearr[i].node;break;}}}}return root;}
};1、第二次解决hard难度的题目，可能还是hard中比较简单的题目。
2、这道题后面的for循环可以用递归的方式解决。
3、重点在于通过深度判断父节点是谁。
（1）如果当前节点的深度大于前一个节点的深度，则当前节点为前一个节点的子节点。
（2）如果当前节点的深度等于前一个节点的深度，则当前节点为前一个节点的兄弟节点（亲兄弟）。
（3）如果当前节点的深度小于前一个节点的深度，则当前节点为前一个节点的父辈节点，所以需要向前找到当前节点的兄弟节点（向前循环第一个深度相等的节点），而且这个兄弟节点一定是父节点的左子节点，所以当前节点是父节点的右节点。
4、这里我自己建立的一个结构体DeTree，也有人用这种方式建立typedef pair<int,int> pos;分别记录深度和节点值，vector<pos>。到我这里可以写成这样：typedef pair<TreeNode*,int> DeTree，分别记录节点地址和深度，vector<DeTree>。