首页 › Java论坛 › 剑指offer-61、序列化二叉树

华佗 發表於 2026-1-8 09:00:00

剑指offer-61、序列化二叉树

<h2 id="题描述">题⽬描述</h2>
<p>请实现两个函数，分别⽤来序列化和反序列化⼆叉树</p>
<p>⼆叉树的序列化是指：把⼀棵⼆叉树按照某种遍历⽅式的结果以某种格式保存为字符串，从⽽使得内存中建⽴起来的⼆叉树可以持久保存。序列化可以基于先序、中序、后序、层序的⼆叉树遍历⽅式来进⾏修改，序列化的结果是⼀个字符串，序列化时通过 某种符号表示空节点（ # ），以 ！ 表示⼀个结点值的结束（ value! ）。</p>
<p>⼆叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str ，重构⼆叉树。例如，我们可以把⼀个只有根节点为1的⼆叉树序列化为" 1"，然后通过⾃⼰的函数来解析回这个⼆叉树</p>
<p>示例1<br>
输⼊：{8,6,10,5,7,9,11}<br>
返回值：{8,6,10,5,7,9,11}</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="前序遍历递归">前序遍历（递归）</h3>
<p>利用二叉树的前序遍历顺序（根-左-右）进行序列化，并使用特殊字符（如"#"或"null"）表示空节点，以确保树结构的唯一性。</p>
<p><strong>序列化思路</strong>：从根节点开始，先输出当前节点的值，然后递归地序列化左子树和右子树。遇到空节点时，输出空标记（如"#"）。</p>
<p><strong>反序列化思路</strong>：按照前序遍历的顺序，依次从序列化字符串中读取节点值。如果读取到空标记，则返回null；否则，用当前值创建节点，并递归构建其左子树和右子树</p>
<pre><code class="language-java">public class CodecPreOrder {

    // 序列化：将二叉树转换为字符串
    public String serialize(TreeNode root) {
      StringBuilder sb = new StringBuilder();
      buildString(root, sb);
      // 删除末尾多余的分隔符（如果有）
      if (sb.length() &gt; 0) {
            sb.setLength(sb.length() - 1);
      }
      return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
      if (node == null) {
            sb.append("#").append(","); // 使用"#"表示空节点
            return;
      }
      sb.append(node.val).append(","); // 先处理根节点
      buildString(node.left, sb);   // 再递归处理左子树
      buildString(node.right, sb);    // 最后递归处理右子树
    }

    // 反序列化：将字符串还原为二叉树
    public TreeNode deserialize(String data) {
      if (data == null || data.isEmpty()) return null;
      // 将字符串按分隔符分割成列表
      LinkedList&lt;String&gt; nodes = new LinkedList&lt;&gt;(Arrays.asList(data.split(",")));
      return buildTree(nodes);
    }

    private TreeNode buildTree(LinkedList&lt;String&gt; nodes) {
      if (nodes.isEmpty()) return null;
      String val = nodes.removeFirst(); // 按前序顺序取出节点值
      if (val.equals("#")) return null; // 遇到空标记则返回null
      
      TreeNode root = new TreeNode(Integer.parseInt(val));
      root.left = buildTree(nodes);// 递归构建左子树
      root.right = buildTree(nodes); // 递归构建右子树
      return root;
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个节点恰好被访问一次。</li>
<li><strong>空间复杂度</strong>：O(n)，递归调用栈的深度在最坏情况下（树退化为链表）为O(n)，序列化字符串长度也与节点数n成线性关系。</li>
</ul>
<h3 id="层序遍历迭代">层序遍历（迭代）</h3>
<p>层序遍历（广度优先搜索）更直观，可以按层级顺序处理节点，适合处理接近完全二叉树的情况。</p>
<p><strong>序列化思路</strong>：使用队列辅助进行层序遍历。从根节点开始，将节点值加入字符串，并将其非空子节点（即使是空节点也记录）加入队列，以确保树结构信息完整。</p>
<p><strong>反序列化思路</strong>：同样使用队列，根据序列化字符串的顺序，依次为每个非空节点创建其左右子节点</p>
<pre><code class="language-java">public class CodecLevelOrder {

    // 序列化：层序遍历二叉树
    public String serialize(TreeNode root) {
      if (root == null) return "";
      StringBuilder sb = new StringBuilder();
      Queue&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;();
      queue.offer(root);
      
      while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,"); // 空节点标记
                continue;
            }
            sb.append(node.val).append(",");
            // 即使子节点为空也加入队列，以保留结构信息
            queue.offer(node.left);
            queue.offer(node.right);
      }
      // 移除末尾多余的分隔符
      sb.setLength(sb.length() - 1);
      return sb.toString();
    }

    // 反序列化：根据层序序列重建树
    public TreeNode deserialize(String data) {
      if (data == null || data.isEmpty()) return null;
      String[] values = data.split(",");
      if (values.equals("#")) return null;
      
      TreeNode root = new TreeNode(Integer.parseInt(values));
      Queue&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;();
      queue.offer(root);
      int index = 1; // 指向当前待处理子节点的数组位置
      
      while (!queue.isEmpty() &amp;&amp; index &lt; values.length) {
            TreeNode parent = queue.poll();
            // 构建左子节点
            if (index &lt; values.length &amp;&amp; !values.equals("#")) {
                parent.left = new TreeNode(Integer.parseInt(values));
                queue.offer(parent.left);
            }
            index++;
            // 构建右子节点
            if (index &lt; values.length &amp;&amp; !values.equals("#")) {
                parent.right = new TreeNode(Integer.parseInt(values));
                queue.offer(parent.right);
            }
            index++;
      }
      return root;
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个节点入队、出队各一次。</li>
<li><strong>空间复杂度</strong>：O(n)，队列中最多同时存储约n/2个节点（完全二叉树的最后一层）。</li>
</ul>
<h3 id="二叉搜索树bst前序优化">二叉搜索树（BST）前序优化</h3>
<p>对于二叉搜索树（BST），可以利用其<strong>中序遍历为升序</strong>的特性，仅通过前序或后序序列即可唯一确定树结构，无需显式存储空节点。</p>
<p><strong>序列化思路</strong>：对BST进行前序遍历，将节点值拼接成字符串。由于BST的性质，中序遍历就是节点值的升序排列，因此仅凭前序遍历结果就能唯一确定树结构。</p>
<p><strong>反序列化思路</strong>：根据前序遍历结果，第一个元素为根节点。剩余元素中，所有小于根节点的值构成左子树的前序遍历，大于根节点的值构成右子树的前序遍历。递归进行即可重建BST</p>
<pre><code class="language-java">public class CodecBST {

    // 序列化：对BST进行前序遍历
    public String serialize(TreeNode root) {
      if (root == null) return "";
      StringBuilder sb = new StringBuilder();
      preorderTraversal(root, sb);
      return sb.substring(0, sb.length() - 1); // 去掉末尾分隔符
    }

    private void preorderTraversal(TreeNode node, StringBuilder sb) {
      if (node == null) return;
      sb.append(node.val).append(" "); // 用空格分隔，注意BST序列化可不显式标记空节点
      preorderTraversal(node.left, sb);
      preorderTraversal(node.right, sb);
    }

    // 反序列化：利用BST性质重建树
    public TreeNode deserialize(String data) {
      if (data.isEmpty()) return null;
      // 将字符串转换为整数列表
      int[] values = Arrays.stream(data.split(" ")).mapToInt(Integer::parseInt).toArray();
      return buildBST(values, 0, values.length - 1);
    }

    private TreeNode buildBST(int[] preorder, int start, int end) {
      if (start &gt; end) return null;
      TreeNode root = new TreeNode(preorder);
      // 找到右子树的开始索引（第一个大于根节点值的元素）
      int rightStart = start + 1;
      while (rightStart &lt;= end &amp;&amp; preorder &lt; preorder) {
            rightStart++;
      }
      // 递归构建左子树和右子树
      root.left = buildBST(preorder, start + 1, rightStart - 1);
      root.right = buildBST(preorder, rightStart, end);
      return root;
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n log n) 最坏情况下（BST退化为链表）为O(n²)，平均情况下为O(n log n)。这是因为在重建过程中，需要为每个节点在序列中查找其左右子树的分界点。</li>
<li><strong>空间复杂度</strong>：O(n)，用于存储递归栈和序列化字符串。</li>
</ul>


</div>
<div id="MySignature" role="contentinfo">
    <p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19431576

查看完整版本: 剑指offer-61、序列化二叉树