LC1028. ecover a Tree From Preorder Traversal 작성일 2019-06-01 https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/ 솔직히 왜 Hard인지 모르겠.. 여튼 평이한 DFS 문제. 1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * 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: string str; int value = -1; int depth = -1; int cur = 0; void next() { if(cur >= str.size()) return; depth = 0; while(str[cur] == '-') depth++, cur++; value = 0; while(isdigit(str[cur])) value = value*10 + str[cur++] - '0'; } TreeNode* dfs(int lv) { if(value == -1) next(); TreeNode* node; if(depth == lv) { node = new TreeNode(value); value = -1; depth = -1; } else return nullptr; node->left = dfs(lv+1); node->right = dfs(lv+1); return node; } TreeNode* recoverFromPreorder(string S) { str = S; return dfs(0); } };