劍指Offer——序列化二叉樹（JS實作）

題目描述

解題思路（序列化）

• 本題分為兩個部分：一是序列化二叉樹，二是反序列化二叉樹。
• 序列化二叉樹：将以可二叉樹，變成一個字元串，這個字元串本人剛開始以為是按照題目給的例子得是層序周遊才行，後來看了題解才知道，原來前序周遊也可以，下面的解法是采用的層序周遊，層序周遊使用的是數組存儲每一層的下一層元素，然後将這個數組變成循環的條件，知道數組為空

序列化代碼

const serialize = (root) => {
    if (!root) return [];
    let queue = [root];
    const res = [];
    while (queue.length !== 0) {
        const temp = [];
        for (let v of queue) {
            res.push(v);
            if (v === 'null') continue;
            if (v.left !== null) {
                temp.push(v.left);            
            } else {
                temp.push('null');
            }
            if (v.right !== null) {
                temp.push(v.right);
            } else {
                temp.push('null');
            }
        }
        queue = temp;    
    }
    let resString = ''
    for (let v of res) {
        if (v instanceof Object) {
            resString = resString + v.val + ',';
        } else {
            resString = resString + v + ',';
        }
    }
    return resString;
};
      

解題思路（反序列化）

• 反序列化是本題的難點，下面的代碼，以後可以作為一個常用函數，輸入二叉樹的層序周遊的字元串，即可生成二叉樹的資料結構
• 反序列化采用的是隊列 + 多指針的思想
• 采用一号指針指向隊頭指針指向原數組的位置
• 采用二号指針指向隊頭指針的left和right指向原數組的位置
• 初始時，二号指針指向下标1，一号指針指向下标0
• 隊頭周遊完之後，将左右指針域的元素入隊
• 直至所有元素周遊完，結束循環，傳回頭指針

反序列化代碼

const deserialize = (data) => {
    if (data.length === 0) return null;
    const list = data.split(',');   // split成數組
    list.splice(list.length-1);
    let list_Pointer = 1;
    let queue_pointer = 0;
    const root = new TreeNode(list[0])
    let queue = [root];

    while (list_Pointer !== list.length) {
        if (queue[0] === null) {
            queue.shift();
            queue_pointer++;
            continue;
        }
        if (queue_pointer === list_Pointer) {
            list_Pointer = list_Pointer + 2;
        }
        if (list[list_Pointer] === 'null') {
            queue[0].left = null;
        } else {
            queue[0].left = new TreeNode(list[list_Pointer]);
        }
        if (list[list_Pointer + 1] === 'null') {
            queue[0].right = null;
        } else {
            queue[0].right = new TreeNode(list[list_Pointer + 1]);
        }
        queue.push(queue[0].left);
        queue.push(queue[0].right);
        queue.shift();
        queue_pointer++
        list_Pointer = list_Pointer + 2;
    }
    return root
};
      

總結（本題給我們的啟示思路）

• 啟示一：學會使用隊列+數組進行二叉樹的層序周遊
• 啟示二：學會使用隊列+多指針将一個字元串生成二叉樹JS的資料結構