1028: Recover-a-Tree-From-Preorder-Traversal
Hard
Very doable “Hard” question.
Key thing that I realised that, if I have a node of depth
n, then the parent is always the
most recently defined node of depth n-1 (since we are
dealing with depth-first search).
Therefore, we can just store every node pointer inside an array, where its index is equal to its depth:
Code:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int returnInt(string& traversal, int& index) {
string stringNum = "";
while (index < traversal.size() && traversal[index] != '-') {
stringNum += traversal[index];
++index;
}
return stoi(stringNum);
}
int returnLayer(string& traversal, int& index) {
int layerNum = 0;
while (index < traversal.size() && traversal[index] == '-') {
++layerNum;
++index;
}
return layerNum;
}
public:
TreeNode* recoverFromPreorder(string traversal) {
TreeNode* root = new TreeNode();
vector<TreeNode*> depths;
depths.push_back(root);
int index = 0;
root -> val = returnInt(traversal, index);
for (index; index < traversal.size(); index) {
int value = returnLayer(traversal, index);
TreeNode* ptr = depths[value-1];
if (ptr -> left) {
ptr -> right = new TreeNode(returnInt(traversal, index));
if (depths.size() > value) {
depths[value] = ptr->right;
} else {
depths.push_back(ptr->right);
}
} else {
ptr -> left = new TreeNode(returnInt(traversal, index));
if (depths.size() > value) {
depths[value] = ptr->left;
} else {
depths.push_back(ptr->left);
}
}
}
return root;
}
};