leecode学习笔记-建树/序列化树

https://www.programmercarl.com/%E5%89%8D%E5%BA%8F/ACM%E6%A8%A1%E5%BC%8F%E5%A6%82%E4%BD%95%E6%9E%84%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91.html

// 根据数组构造二叉树
TreeNode* construct_binary_tree(const vector& vec) {
    vector vecTree (vec.size(), NULL);
    TreeNode* root = NULL;
    // 把输入数值数组，先转化为二叉树节点数组
    for (int i = 0; i < vec.size(); i++) {
        TreeNode* node = NULL;
        if (vec[i] != -1) node = new TreeNode(vec[i]); // 用 -1 表示null
        vecTree[i] = node;
        if (i == 0) root = node;
    }
    // 遍历一遍，根据规则左右孩子赋值就可以了
    // 注意这里 结束规则是 i * 2 + 2 < vec.size()，避免空指针
    for (int i = 0; i * 2 + 2 < vec.size(); i++) {
        if (vecTree[i] != NULL) {
            // 线性存储转连式存储关键逻辑
            vecTree[i]->left = vecTree[i * 2 + 1];
            vecTree[i]->right = vecTree[i * 2 + 2];
        }
    }
    return root;
}

递归：

public class Codec {
    StringBuilder sb = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        sb.append("[");
        recur(root);
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    void recur(TreeNode root) {
        if (root == null) {
            sb.append("null,");
            return;
        }
        
        sb.append(root.val + ",");
    
        recur(root.left);
        recur(root.right);    
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.equals("[]")) return null;
        Queue que = new LinkedList<>();
        String[] sArray = data.substring(1, data.length() - 1).split(",");
        for (String s : sArray) {
            que.offer(s);
        }

        return recurbuild(que);

    }

    TreeNode recurbuild(Queue que) {
        String temp = que.poll();
        if (temp.equals("null")) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(temp));

        root.left = recurbuild(que);
        root.right = recurbuild(que);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

层序遍历：

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        Queue que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (node != null) {
                sb.append(node.val + ",");
                que.add(node.left);
                que.add(node.right);
            } else {
                sb.append("null,");
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] val = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(val[0]));
        Queue que = new LinkedList<>();
        que.add(root);
        int i = 1;
        while (!que.isEmpty()) {
            TreeNode temp = que.poll();
            if (!val[i].equals("null")) {
                temp.left = new TreeNode(Integer.parseInt(val[i]));
                que.add(temp.left);
            }
            i++;
            if (!val[i].equals("null")) {
                temp.right = new TreeNode(Integer.parseInt(val[i]));
                que.add(temp.right);
            }
            i++;
        }
        return root;       
    }
}