解法1.层序遍历，bfs , java\c++

解法2：先序遍历，dfs, java\c++

解法3：后序遍历, dfs, java\c++

//解法1.层序遍历，bfs , java\c++
//解法2：先序遍历，dfs, java\c++
//解法3：后序遍历, dfs, java\c++

//解法1.层序遍历，bfs , java\c++
//java
class Solution {
    // Encodes a tree to a single string.
    String serialize(TreeNode root) {
        //首先进行特判
        if(root == null) return "null";
        String res = root.val + " ";

        //层序遍历，bfs遍历二叉树所有节点
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode t = q.poll();
            // if(t == null)   continue;
            if(t.left == null)    res += "null ";
            else{
                res += t.left.val + " ";
                q.add(t.left);
            } 
            if(t.right == null) res += "null ";
            else{
                res += t.right.val +" ";
                q.add(t.right);
            }
        }
        // System.out.println(res);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode deserialize(String data) {
        String[] arr = data.split(" ");
        int idx = 0;
        Queue<TreeNode> q = new LinkedList<>();

        TreeNode root = getNode(arr[idx++]);
        if(root != null)  q.add(root);
        TreeNode cur = null;

        while(!q.isEmpty()){
            cur = q.poll();
            TreeNode left = getNode(arr[idx++]);
            TreeNode right = getNode(arr[idx++]);
            cur.left = left;
            cur.right = right;
            if(left != null) q.add(left);
            if(right != null) q.add(right);
        }
        return root;

    }
    TreeNode getNode(String val){
        if(val.equals("null")) return null;
        return new TreeNode(Integer.valueOf(val));
    }
}

//c++层序遍历
/**
 * 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:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "n ";
        string res = to_string(root->val) + " ";
        queue<TreeNode*> q ;
        q.push(root);
        auto cur = new TreeNode(-1);
        while(q.size()){
            cur = q.front();
            q.pop();

            if(cur->left){
                res += to_string(cur->left->val) + " ";
                q.push(cur->left);
            }else res += "n "; 

            if(cur->right){
                res += to_string(cur->right->val) + " ";
                q.push(cur->right);
            }else res += "n ";
        }
        // cout<< res <<endl;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        // int n = data.size();
        // if(data.size()) return NULL;
        int u = 0, k = 0;
        while(data[k] != ' ') k++;
        if(data[u] == 'n') return NULL;
        auto root = getNode(data, u, k);
        u = k + 1;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            auto cur = q.front();
            q.pop();

            //先找左子节点
            if(data[u] == 'n'){
                cur->left = nullptr;
                u += 2;
            }else{
                int k = u;
                while(data[k] != ' ') k ++;
                auto left = getNode(data, u, k);
                cur->left = left;
                q.push(left);
                u = k + 1;
            }
            //再找右子节点
            if(data[u] == 'n'){
                cur->right = nullptr;
                u += 2;
            }else{
                int k = u;
                while(data[k] != ' ') k ++;
                auto right = getNode(data, u, k);
                cur->right = right;
                q.push(right);
                u = k + 1;
            }
        }
        return root;
    }
    TreeNode* getNode(string &data, int l, int r){
        int val = 0;
        bool flag = false;
        for(int i = l; i < r; i++) {
            if(data[i] == '-'){
                flag = true;
                continue;
            } 
            val = val * 10 + data[i] - '0';
        }
        if(flag) val = -val;
        // cout<< l<<" "<< " "<< r<< " " << val <<endl;
        return new TreeNode(val);
    }
};

//解法2：先序遍历，dfs
//java
//先序遍历，dfs(根->左->右)
class Solution {

    // Encodes a tree to a single string.
    private static StringBuffer res = new StringBuffer();
    String serialize(TreeNode root) {
        dfs_e(root);
        // System.out.println(res);
        return res.toString();
    }
    void dfs_e(TreeNode root){
        if(root == null){ 
            res.append("n ");
            return;
        }
        res.append(root.val+" ");
        dfs_e(root.left);
        dfs_e(root.right);
    }

    // Decodes your encoded data to tree.
    private static String[] arr;
    private static int n;
    private static int idx = 0;
    TreeNode deserialize(String data) {
        arr = data.split(" ");
        // for(String st: arr) System.out.print(st);
        n = arr.length;
        TreeNode root = dfs_d(idx);
        return root;
    }
    //这里一定要注意形参和实参的区分
    TreeNode dfs_d(int u){
        if(u == n) return null;

        if(arr[u].equals("n")){
            idx++;
            return null;
        }    
        int val = Integer.valueOf(arr[u]);
        idx ++;
        TreeNode root = new TreeNode(val);
        TreeNode left = dfs_d(idx);
        TreeNode right = dfs_d(idx);
        root.left = left;
        root.right = right;
        return root;
    }
}

//c++
 //先序：根 -> 左 -> 右
class Solution {
public:
    // Encodes a tree to a single string.
    string res;
    string serialize(TreeNode* root) {
        dfs_e(root);
        // cout<< res<< endl;
        return res;
    }
    void dfs_e(TreeNode* root){
        if(!root){
            res += "n ";
            return;
        } 
        res += to_string(root->val) + " ";
        dfs_e(root->left);
        dfs_e(root->right);
    }

    // Decodes your encoded data to tree.
    int n;
    TreeNode* deserialize(string data) {
        n = data.size();
        int u = 0;
        auto res = dfs_d(data, u);
        return res;
    }
    TreeNode* dfs_d(string data, int &u){
        if(u == n) return nullptr;

        int k = u;
        while(data[k] != ' ') k++;
        //如果当前节点为空节点
        if(data[u] == 'n'){
            u = k + 1;
            return nullptr;
        } 
        //如果当前节点不为空
        int val = 0;
        bool flag = false;
        for(int i = u; i < k; i++){
            if(data[i] == '-'){
                flag = true;
                continue;
            }
            val = val * 10 + data[i] - '0';
        } 
        if(flag) val = - val;
        auto root = new TreeNode(val);
        u = k + 1;
        auto left = dfs_d(data, u);
        auto right = dfs_d(data, u);
        root->left = left;
        root->right = right;
        return root;
    }
};

//解法3：后序遍历, dfs, java\c++
//后序遍历，dfs(左->右->根),方法基本上同先序遍历
//区别在于序列化的时候要按照(根->右->左)的顺序将后遍历到的节点插入到序列的最前端
//在反序列化的时候，要从序列的最后一个元素开始往前遍历，同样生成节点也要按照(根->右->左)的顺序

//java
class Solution {

    // Encodes a tree to a single string.
    private static StringBuffer res = new StringBuffer();
    String serialize(TreeNode root) {
        dfs_e(root);
        // System.out.println(res);
        return res.toString();
    }
    void dfs_e(TreeNode root){
        if(root == null){ 
            res.insert(0, "n ");
            return;
        }
        res.insert(0, root.val+" ");
        dfs_e(root.right);
        dfs_e(root.left);
    }

    // Decodes your encoded data to tree.
    private static String[] arr;
    private static int n;
    private static int idx;
    TreeNode deserialize(String data) {
        arr = data.split(" ");
        // for(String st: arr) System.out.print(st);
        n = arr.length;
        idx = n - 1;
        TreeNode root = dfs_d(idx);
        return root;
    }
    TreeNode dfs_d(int u){
        if(u == -1) return null;

        if(arr[u].equals("n")){
            idx--;
            return null;
        }    
        int val = Integer.valueOf(arr[u]);
        idx --;
        TreeNode root = new TreeNode(val);
        TreeNode right = dfs_d(idx);
        TreeNode left = dfs_d(idx);
        root.left = left;
        root.right = right;
        return root;
    }
}
//c++