C++ 迭代实现，无递归

C++ 迭代实现，无递归

class Solution {
public:
    string str;
    char* Serialize(TreeNode *root) {  
        if(root == nullptr)
            return nullptr;
            char* res;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            if(node == nullptr)
                str += "#!";
            else {
                str += to_string(node->val);
                str += "!";
                stk.push(node->right);
                stk.push(node->left);
            }
        }
        res = const_cast<char*>(str.c_str());
        return res;
    }
    TreeNode* Deserialize(char *str) {
        if(str == nullptr)
            return nullptr;
        char** s_str = &str;
        vector<char*> v;
        //将字符串分割 装进vector
        while(**s_str != '\0') {
            char* c = strtok(*s_str, "!");
            v.push_back(c);
            *s_str += (strlen(c) + 1);
        }
        stack<TreeNode*> stk;
        TreeNode* root = new TreeNode(atoi(v[0]));
        TreeNode* node = root;
        int index = 0;
        while(!stk.empty() || node != nullptr) {
            while(node && index+1 < v.size()) { //当前节点非空
                stk.push(node);//将节点加入栈中 - 非空节点
                if(index+1 < v.size() && (strcmp(v[index+1], "#") != 0)) {
                    TreeNode* child = new TreeNode(atoi(v[index+1]));
                    node->left = child;//不断构造左节点
                }
                node = node->left;
                index++;                   
            }
            //当左子树遍历完最后一个叶子节点时
            node = stk.top(); //取出上个节点
            if(index+1 < v.size() && (strcmp(v[index+1], "#") != 0)) {
                TreeNode* child = new TreeNode(atoi(v[index+1]));
                node->right = child; //构造右节点
            }
            stk.pop();//当前节点的左右子节点均构造完成，可以弹出
            node = node->right; //以当右节点为新的节点
            index++;
        }
        return root;   
    }
};