LeetCode Weekly Contest 132 : 1028. Recover a Tree From Preorder Traversal

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

問題

各ノードに整数値を持つ二分木がある。
この木をPreorder順にDFSした際、訪問したノードの深さと値の情報が与えられる。
元の値を復元せよ。

解法

DFSすら必要なくて、訪問中のノードの階層関係をスタックで管理し、順次本問先ノードをその１つ上の深さのノードに子要素として接続するだけ。

class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        vector<int> V;
        FORR(c,S) {
			if(c=='-') {
				if(V.back()>=0) V.push_back(-1);
				else V.back()--;
			}
			else {
				if(V.empty() || V.back()<0) V.push_back(c-'0');
				else V.back()=V.back()*10+c-'0';
			}
		}
		vector<TreeNode*> ST;
		ST.push_back(new TreeNode(V[0]));
		for(int i=1;i<V.size();i+=2) {
			int d=-V[i];
			int v=V[i+1];
			while(ST.size()>d) ST.pop_back();
			if(ST.back()->left==NULL) {
				ST.back()->left=new TreeNode(v);
				ST.push_back(ST.back()->left);
			}
			else {
				ST.back()->right=new TreeNode(v);
				ST.push_back(ST.back()->right);
			}
		}
		return ST[0];
        
    }
};

まとめ

LeetCodeの二分木の問題、今まで面白いと思えたものが１個もないのでどうにかしてほしい…。