前言

想要精通算法和SQL的成長(zhǎng)之路 - 系列導(dǎo)航

一. 二叉樹的層序遍歷（BFS）

二叉樹的層序遍歷

像這種從上至下并且按層打印的，可以稱之為二叉樹的廣度優(yōu)先搜索（BFS）。而這類算法往往借助隊(duì)列的一個(gè)先入先出特性來(lái)實(shí)現(xiàn)。

那么有這么幾個(gè)步驟：
1.特殊處理還有初始化動(dòng)作。

List<List<Integer>> res = new ArrayList<>();
// 樹為空，返回空數(shù)組
if (root == null) {
    return res;
}
// 初始化隊(duì)列
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);

2.BFS循環(huán)：

while (!queue.isEmpty()) {
    // 該層的打印結(jié)果
    ArrayList<Integer> tmp = new ArrayList<>();
    // 將當(dāng)前層（隊(duì)列內(nèi)的元素）全部打印
    for (int i = queue.size(); i > 0; i--) {
        // 隊(duì)首先出
        TreeNode node = queue.poll();
        tmp.add(node.val);
        // 從左往右添加元素（先進(jìn)先出）
        if (node.left != null) {
            tmp.add(node.left.val);
        }
        if (node.right != null) {
            tmp.add(node.right.val);
        }
    }
    // 當(dāng)前層的遍歷結(jié)果加入到最終結(jié)果集中
    res.add(tmp);
}

最終完整代碼如下：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    // 樹為空，返回空數(shù)組
    if (root == null) {
        return res;
    }
    // 初始化隊(duì)列
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 該層的打印結(jié)果
        ArrayList<Integer> tmp = new ArrayList<>();
        // 將當(dāng)前層（隊(duì)列內(nèi)的元素）全部打印
        for (int i = queue.size(); i > 0; i--) {
            // 隊(duì)首先出
            TreeNode node = queue.poll();
            tmp.add(node.val);
            // 從左往右添加元素（先進(jìn)先出）
            if (node.left != null) {
                tmp.add(node.left.val);
            }
            if (node.right != null) {
                tmp.add(node.right.val);
            }
        }
        // 當(dāng)前層的遍歷結(jié)果加入到最終結(jié)果集中
        res.add(tmp);
    }
    return res;
}

二. 二叉樹的序列化與反序列化

原題鏈接

從題目來(lái)看，序列化的操作就是：從上往下，從左往右的一個(gè)層級(jí)遍歷。那么在做這個(gè)題目之前，我們可以看下這個(gè)題目：

那么我們回歸本題，本題和1.1小節(jié)的題目有啥不同？

• 如果是空節(jié)點(diǎn)，我們要輸出null。
• 我們還要根據(jù)序列化的結(jié)果，反序列化回一顆二叉樹。

我們依舊可以使用隊(duì)列來(lái)解決。

2.1 序列化操作

首先，特判以及隊(duì)列的初始化操作：

if (root == null) {
    return "[]";
}
StringBuilder res = new StringBuilder("[");
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);

順帶提一嘴，希望大家養(yǎng)成良好的編碼習(xí)慣，關(guān)于字符串的equal比較，常量放在前面，變量放后面，避免不必要的空指針。

BFS遞歸操作：

while (!queue.isEmpty()) {
    // 隊(duì)列先進(jìn)先出，從隊(duì)首開始出隊(duì)
    for (int i = queue.size(); i > 0; i--) {
        TreeNode node = queue.poll();
        // 只不過(guò)這里多加了一個(gè)判斷而已，如果是空節(jié)點(diǎn)，我們添加null
        if (node == null) {
            res.append("null,");
            continue;
        }
        // 否則，非空，添加當(dāng)前節(jié)點(diǎn)的值
        res.append(node.val + ",");
        // 由于上面已經(jīng)加了null的判斷了，這里直接按順序先加左節(jié)點(diǎn)，再加右節(jié)點(diǎn)即可。
        queue.add(node.left);
        queue.add(node.right);
    }
}

最后就是收尾工作：我們對(duì)于結(jié)尾的值，要把多余的逗號(hào)去除。

// 刪除最后一個(gè)多余的逗號(hào)
res.deleteCharAt(res.length() - 1);
res.append("]");
return res.toString();

最終完整代碼如下：

public String serialize(TreeNode root) {
    if (root == null) {
        return "[]";
    }
    StringBuilder res = new StringBuilder("[");
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        // 隊(duì)列先進(jìn)先出，從隊(duì)首開始出隊(duì)
        for (int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            // 只不過(guò)這里多加了一個(gè)判斷而已，如果是空節(jié)點(diǎn)，我們添加null
            if (node == null) {
                res.append("null,");
                continue;
            }
            // 否則，非空，添加當(dāng)前節(jié)點(diǎn)的值
            res.append(node.val + ",");
            // 由于上面已經(jīng)加了null的判斷了，這里直接按順序先加左節(jié)點(diǎn)，再加右節(jié)點(diǎn)即可。
            queue.add(node.left);
            queue.add(node.right);
        }
    }
    // 刪除最后一個(gè)多余的逗號(hào)
    res.deleteCharAt(res.length() - 1);
    res.append("]");
    return res.toString();
}

2.2 反序列化操作

同樣地，特判以及隊(duì)列的初始化操作：

if ("[]".equals(data)) {
    return null;
}
// 各個(gè)節(jié)點(diǎn)的值
String[] vals = data.substring(1, data.length() - 1).split(",");
// 第一個(gè)值必定是根節(jié)點(diǎn)（從上往下的特性）
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
LinkedList<TreeNode> queue = new LinkedList<TreeNode>() {{
    add(root);
}};

BFS操作：

int index = 1;
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    // 處理左節(jié)點(diǎn)
    if (!"null".equals(vals[index])) {
        node.left = new TreeNode(Integer.parseInt(vals[index]));
        queue.add(node.left);
    }
    // 這里不管怎樣都是要往后移動(dòng)一位，如果是null，我們node.left就默認(rèn)是null了。
    index++;
    if (!"null".equals(vals[index])) {
        node.right = new TreeNode(Integer.parseInt(vals[index]));
        queue.add(node.right);
    }
    index++;
}

完整代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-729060.html

public TreeNode deserialize(String data) {
    if ("[]".equals(data)) {
        return null;
    }
    String[] vals = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>() {{
        add(root);
    }};
    int index = 1;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // 處理左節(jié)點(diǎn)
        if (!"null".equals(vals[index])) {
            node.left = new TreeNode(Integer.parseInt(vals[index]));
            queue.add(node.left);
        }
        // 這里不管怎樣都是要往后移動(dòng)一位，如果是null，我們node.left就默認(rèn)是null了。
        index++;
        if (!"null".equals(vals[index])) {
            node.right = new TreeNode(Integer.parseInt(vals[index]));
            queue.add(node.right);
        }
        index++;
    }
    return root;
}

到了這里，關(guān)于想要精通算法和SQL的成長(zhǎng)之路 - 二叉樹的序列化和反序列化問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！