Recover a Tree From Preorder Traversal [LeetCode 1028]

https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/

二分木がある。
これをpreorder dfsで探索して、[深さ][頂点に書かれている数]を順番に書いてつなげた文字列が与えられる。
preorder dfsはある頂点に来たら、左辺に移動して、戻ってきたら右辺に移動して、戻ってきたら親に戻る感じ。
深さは深さの分だけ-をつなげたもの。
　
ここから、二分木を復元せよ。
（問題のOutputはよく分からん表記になっているが、この問題で使われているTreeNode構造体で答える。
なので、TreeNode構造体の練習のためにもこっちの問題からやるといい。

頂点数≦1000

前提知識

• 構文解析

解説

https://leetcode.com/contest/weekly-contest-132/submissions/detail/222253700/

アルゴリズムとして難しいというのはあまりなくて、構文解析力を問う問題。
　
（怖いので終端文字として"#"を追加しているが、必要ないかもしれない）
基本は頭から、-の数を数えて深さを取ってきて、その後に続く数を見て、頂点の数を取ってきて、それをNodeとして作って、子供を見に行って…というのを繰り返せばいい。
あるNodeの子のNodeは深さが親+1になっている必要がある。
もし、構文解析したときにそうなっていない場合は、そのNodeの子ではなかったということになる。
そのNodeの子ではなかったということは、そのNodeの祖先のどれかの子であったということである。
つまり、あるNodeの子としてパースしても、深さが合致しなかった場合はロールバックして、祖先に処理を渡す必要が出てくる。
つらつら書いたが、結論としては、変数bakにパース前の添字を覚えておき、今作りたい深さと合致しない場合は、パース前の添字に戻して、処理を戻すような処理を追加する。
あとは、雰囲気で適当に書けば通る。
　
もし、バグり過ぎて通らない場合は、木構造を作る練習をまずするといいかもしれない。
構文解析系でNodeを自分で構築していく系は割と見るので、そこら編も練習に使えるかもしれない。
どっちにしろ、LeetCodeでこの辺の練習をするのは辛いので、他で練習してから戻ってくるといいだろう。

class Solution {
public:
	
	TreeNode* dfs(string& S, int& idx, int dpt) {
		int bak = idx;

		int d = 0;
		while (S[idx] == '-') {
			d++;
			idx++;
		}

		int num = 0;
		while ('0' <= S[idx] and S[idx] <= '9') {
			num = num * 10 + S[idx] - '0';
			idx++;
		}

		if (dpt != d) {
			idx = bak;
			return NULL;
		}

		TreeNode* res = new TreeNode(num);

		res->left = dfs(S, idx, dpt + 1);
		res->right = dfs(S, idx, dpt + 1);

		return res;

	}
	TreeNode* recoverFromPreorder(string S) {
		int N = S.length();
		S += "#";
		int i = 0;

		return dfs(S, i, 0);
	}
};