[leetCode] 297. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Serialize and Deserialize Binary Tree - LeetCode

 

이 문제는 string을 트리로, 트리를 string으로 변화하는 직렬화, 역직렬화하는 문제이다.

 

먼저 아래는 직렬화에 대한 코드이다.

string serialize(TreeNode* root)
{
    if (!root) 
        return "null";
	
    vector<string> v;
	queue<TreeNode*> q;
	q.push(root);

	int count = 0;
	while (!q.empty())
	{
		int levelSize = q.size();
		count = 0;
		for (int i = 0; i < levelSize; i++)
		{
			TreeNode* node = q.front();
			q.pop();

			if (node == nullptr)
			{
				v.push_back("null,");
				count++;
				if (count == levelSize)
				{
					for (int j = 0; j < count; j++)
					{
						v.pop_back();
					}
				}
				continue;
			}
			v.push_back(to_string(node->val) + ",");

			if (node->left != nullptr)
			{
				q.push(node->left);
			}
			else
			{
				q.push(nullptr);
			}

			if (node->right != nullptr)
			{
				q.push(node->right);
			}
			else
			{
				q.push(nullptr);
			}
		}
	}
	string result = std::accumulate(v.begin(), v.end(), string(""));

	if (!result.empty()) {
		result.pop_back();
	}

	return result;
}

 

아래는 역직렬화 하는 코드이다.

TreeNode* deserialize(string data)
{
    if (data == "null")
       return nullptr;
	vector<string> v;

	std::string token = "";

	for (char ch : data) {
		if (ch == ',') {
			v.push_back(token);
			token = "";
		}
		else {
			token += ch;
		}
	}
	v.push_back(token);

	TreeNode* root = new TreeNode(stoi(v[0]));

	queue<TreeNode*> q;
	q.push(root);
	int childStartIndex = 1;
	while (!q.empty())
	{
		int levelSize = q.size();
		int nextLevelNodes = 0;

		for (int i = 0; i < levelSize; i++)
		{
			TreeNode* node = q.front();
			q.pop();

			int leftIdx = childStartIndex + (i * 2);
			int rightIdx = childStartIndex + (i * 2) + 1;

			if (leftIdx >= v.size() || v[leftIdx] == "null")
			{
				node->left = nullptr;
			}
			else
			{
				int push_value = stoi(v[leftIdx]);
				node->left = new TreeNode(push_value);
				q.push(node->left);
				nextLevelNodes++;
			}

			if (rightIdx >= v.size() || v[rightIdx] == "null")
			{
				node->right = nullptr;
			}
			else
			{
				int push_value = stoi(v[rightIdx]);
				node->right = new TreeNode(push_value);
				q.push(node->right);
				nextLevelNodes++;
			}
		}
		childStartIndex += (levelSize * 2);
	}

	return root;
};

근데 코드를 보면 대단히 야매?로 짠 감이 없지 않아 있긴하다.

쓸데없는 for문과 if문이 많은 느낌이 든다.

 

그래서 아래와 같이 수정해 봤다. 

먼저 직렬화코드이다.

 

string serialize(TreeNode* root) {
        if (root == nullptr)
            return "null";

        vector<string> v;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (node == nullptr) {
                v.push_back("null");
            } else {
                v.push_back(to_string(node->val));
                q.push(node->left);
                q.push(node->right);
            }
        }

        while (!v.empty() && v.back() == "null") {
            v.pop_back();
        }

        string result = "";
        for (int i = 0; i < v.size(); i++) {
            result += v[i];
            if (i < v.size() - 1) 
                result += ",";
        }
        return result;
    }

다음은 역직렬화 코드이다

TreeNode* deserialize(string data) {
        if (data.empty() || data == "null") 
            return nullptr;

        vector<string> v;
        string token = "";

        for (char ch : data) 
        {
            if (ch == ',') 
            {
                v.push_back(token);
                token = "";
            } 
            else
            {
                token += ch;
            }
        }
        v.push_back(token);

        TreeNode* root = new TreeNode(stoi(v[0]));
        queue<TreeNode*> q;
        q.push(root);

        int childStartIndex = 1; 

        while (!q.empty()) {
            int levelSize = q.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();

                int leftIdx = childStartIndex + (i * 2);
                int rightIdx = childStartIndex + (i * 2) + 1;

                if (leftIdx >= v.size() || v[leftIdx] == "null" || v[leftIdx] == "")
                {
                    node->left = nullptr;
                } 
                else {
                    node->left = new TreeNode(stoi(v[leftIdx]));
                    q.push(node->left); 
                }

                if (rightIdx >= v.size() || v[rightIdx] == "null" || v[rightIdx] == "") 
                {
                    node->right = nullptr;
                } 
                else {
                    node->right = new TreeNode(stoi(v[rightIdx]));
                    q.push(node->right); 
                }
            }
            childStartIndex += (levelSize * 2); 
        }

        return root;
    }