【基础篇 - Day 17】 2023-03-01 - 297. 二叉树的序列化与反序列化 （03. 树 ）

[threedayAAAAA]

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

 

示例 1：

输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5] 示例 2：

输入：root = [] 输出：[] 示例 3：

输入：root = [1] 输出：[1] 示例 4：

输入：root = [1,2] 输出：[1,2]  

提示：

树中结点数在范围 [0, 104] 内 -1000 <= Node.val <= 1000

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

层序遍历

代码

function serialize(root: TreeNode | null): string {
    if(!root){
        return '#'
    }
    let result = []
    let floor = [root]
    while(floor.length){
        let newFloor = []
        let floorData = []
        floor.forEach(item => {
            if(item === null){
                floorData.push('#')
                return
            } else {
                floorData.push(item.val)
            }
            newFloor.push(item.left)
            newFloor.push(item.right)
        })
        floor = newFloor
        result.push(floorData.join(','))
    }
    return result.join(';')
};

function deserialize(data: string): TreeNode | null {
    const floors = data.split(';')
    if(!floors.length){
        return null
    }
    let result = null
    const topEl = floors.shift()
    result = topEl === '#' ? null : new TreeNode(Number(topEl))
    let curFloor = [result]
    floors.forEach(floor => {
        let newFloor = []
        floor.split(',').forEach((item, index) => {
            const parentNode = curFloor[Math.floor(index / 2)]
            const currentNode = item === '#' ? null : new TreeNode(Number(item))
            if(currentNode){
                newFloor.push(currentNode)
            }
            if(index % 2 === 0){
                parentNode.left = currentNode
            } else {
                parentNode.right = currentNode
            }
        })
        curFloor = newFloor
    })
    return result
};

时空复杂度

• 时间复杂度： O(N)
• 空间复杂度：O(N)

[yunliuyan]

思路

• 序列化： 前序遍历
• 反序列化: 将字符串变为数组，然后出数组队列，当为null则为空树，若存在，先递归左树，再递归右树

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
    let res = '';
    const dfs = (root: TreeNode | null) => {
        if(!root) {
            res += 'null,';
            return;
        }
        res += `${root.val},`
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return res;
};

/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
   const dp = (dataArr: string[]) => {
       const curVal = dataArr.shift();
       if (curVal === 'null') {
           return null;
       }
       const root = new TreeNode(Number(curVal));
       root.left = dp(dataArr);
       root.right = dp(dataArr);
       return root;
   }
   return dp(data.split(','));
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)

[MiumMi]

思路

先层序遍历，把每一层填充满，拼接成最终的字符串 解析的时候按层拆分，每一层去填充上一层节点的left和right

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
    if (!root) {
        return '';
    }
    let queue = [root];
    let result = [];
    while(queue.length) {
        const currentLevel = queue;
        queue = [];
        for(let i = 0; i < currentLevel.length; i++) {
            const temp = currentLevel[i];
            if (temp === null) {
                result.push('$');
            } else {
              result.push(temp.val);
              queue.push(temp.left ?? null);
              queue.push(temp.right ?? null);
            }
        }
        result.push('^');
    }
    return result.join(',');
};

function formatStrToArr (val: string) {
    const arr: string[] = val.split(',');
    return arr.reduce((prev: string[], item: string) => {
        if (item) {
            prev.push(item);
        }
        return prev;
    }, []);
}

/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
    if (!data.length) {
        return null;
    }
    const treeArr = data.split('^');
    let result = null;
    let parentArr = [];
    for (let i = 0; i < treeArr.length; i++) {
        const queueArr = formatStrToArr(treeArr[i]);
        if(!queueArr.length) {
            continue;
        }
        const tempArr = [];
        queueArr.forEach((item, index) => {
            const parentNode = parentArr[Math.floor(index / 2)];
            const currentNode = item === '$' ? null : new TreeNode(Number(item));
            if (currentNode) {
                tempArr.push(currentNode);
            }
            if (i === 0) {
                result = currentNode;
            } else {
                if (index % 2 === 0) {
                    parentNode.left = currentNode;
                } else {
                    parentNode.right = currentNode;
                }
            }
        });
        parentArr = tempArr;
    }
    return result;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

---

分析

时间复杂度：serialize： O(n) deserialize: O(n*m) 空间复杂度：O(n);