二叉树层序遍历、序列化与宽度问题

二叉树是数据结构中的核心内容，其遍历、序列化以及相关的算法问题是面试和学习的重点。本文将结合具体的Java代码实现，探讨几个经典的二叉树算法问题，包括层序遍历、序列化与反序列化、N叉树与二叉树的转换、求解最大宽度、寻找后继节点以及有趣的折纸问题。

1. 二叉树的层序遍历

二叉树的层序遍历（Level-Order Traversal），也称为广度优先搜索（BFS），其核心思想是逐层访问二叉树的节点。

1.1 核心思路

为了实现按层访问，我们通常借助一个队列（Queue）来辅助。

初始化一个队列，并将根节点（root）入队。
当队列不为空时，循环执行以下操作。
从队列中弹出一个节点（记为poll），并访问（例如，打印）该节点的值。
如果该弹出的节点的左孩子不为空，将其左孩子入队。
如果该弹出的节点的右孩子不为空，将其右孩子入队。
循环往复，直到队列为空，即完成了所有节点的层序遍历。

1.2 Java实现

java

package L11;

import java.util.LinkedList;
import java.util.Queue;

public class LevelTraversalBT {

    public static class Node {
        private int val;
        private Node left;
        private Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void levelTraversal(Node root) {
        if (root == null) return;

        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            Node poll = q.poll();
            System.out.print(poll.val + " ");

            if (poll.left != null) q.add(poll.left);
            if (poll.right != null) q.add(poll.right);
        }
        System.out.println();
    }

2. 二叉树的序列化和反序列化

序列化是指将内存中的树结构转换为可以存储或传输的格式（如字符串或队列），反序列化则是相反的过程。关键在于，序列化过程中必须包含空节点（null）的信息，否则无法唯一地重建树的结构。

2.1 先序遍历序列化与反序列化

序列化思路：

采用递归思想。序列化时，先将根节点的值加入结果队列，然后递归序列化其左子树，最后递归序列化其右子树。遇到空节点时，也需要向队列中添加一个null标识。
反序列化思路：

反序列化是一个相匹配的递归过程。我们从序列化队列中依次取出元素。如果取出的值是null，则返回一个空节点。否则，创建一个新节点，并递归地为其构建左子树，然后递归地为其构建右子树。

2.2 后序遍历序列化与反序列化

序列化思路：

后序遍历的顺序是“左、右、根”。同样采用递归，先递归序列化左子树，再递归序列化右子树，最后才将根节点的值加入队列。空节点同样用null标记。
反序列化思路：

这是一个难点。如果直接从队列中按“左、右、根”的顺序取出元素，我们无法构建树，因为必须先构建根节点。

解决方案是先将序列化队列中的所有元素压入一个栈（Stack）。这样，从栈中弹出的顺序就变成了“根、右、左”。此时，我们就可以先构建根节点，然后递归地构建其右子树，最后递归地构建其左子树，从而正确地重建原树。

2.3 层序遍历序列化与反序列化

序列化思路：

这是一种非递归实现。使用一个队列（queue）进行层序遍历，同时用另一个队列（rst）存储序列化结果。

核心在于：处理当前节点（curr）时，无论其左右孩子是否为null，都将相应的值（或null）加入rst队列。但只有非null的孩子才被加入用于遍历的queue队列。
反序列化思路：

反序列化同样借助一个队列（queue）来辅助构建。
1. 先从序列化队列（serial）中取出第一个元素作为根节点，并将根节点加入queue。
2. 当queue不为空时，弹出一个节点记为parent。
3. 从serial里弹出两个元素，分别作为parent的左孩子和右孩子。
4. 如果弹出的值不为null，则创建新节点，设为parent的子节点，并将新节点加入queue，以便后续处理它的孩子。

2.4 Java实现

java

package L11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SerializeAndReconstructTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
	
    // 先序遍历序列化
    public static Queue<String> preSerial(Node root) {
        Queue<String> rst = new LinkedList<>();
        preSerialProcess(root, rst);
        return rst;
    }

    private static void preSerialProcess(Node root, Queue<String> rst) {
        if (root == null) {
            rst.add(null);
        } else {
            rst.add(String.valueOf(root.value));
            preSerialProcess(root.left, rst);
            preSerialProcess(root.right, rst);
        }
    }
	
    // 先序遍历反序列化
    public static Node preBuild(Queue<String> serial) {
        if (serial == null || serial.isEmpty()) {
            return null;
        }

        String val = serial.poll();
        if (val == null) {
            return null;
        }
        Node curr = new Node(Integer.parseInt(val));
        curr.left = preBuild(serial);
        curr.right = preBuild(serial);

        return curr;
    }

    // 后序遍历序列化
    public static Queue<String> posSerial(Node root) {
        Queue<String> rst = new LinkedList<>();
        posSerialProcess(root, rst);
        return rst;
    }

    private static void posSerialProcess(Node root, Queue<String> rst) {
        if (root == null) {
            rst.add(null);
        } else {
            posSerialProcess(root.left, rst);
            posSerialProcess(root.right, rst);
            rst.add(String.valueOf(root.value));
        }
    }
	
    // 后序遍历反序列化
    public static Node posBuild(Queue<String> serial) {
        if (serial == null || serial.isEmpty()) return null;

        Stack<String> s = new Stack<>();
        for(String item : serial) {
            s.push(item);
        }

        return posBuildProcess(s);
    }

    private static Node posBuildProcess(Stack<String> s) {
        String pop = s.pop();
        if (pop == null) {
            return null;
        }

        Node root = new Node(Integer.parseInt(pop));
        root.right = posBuildProcess(s);
        root.left = posBuildProcess(s);

        return root;
    }

    // 层序遍历序列化
    public static Queue<String> levelSerial(Node root) {
        Queue<Node> queue = new LinkedList<>();
        Queue<String> rst = new LinkedList<>();

        if (root == null) {
            rst.add(null);
            return rst;
        }

        queue.add(root);
        rst.add(String.valueOf(root.value));

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            if (curr.left == null) {
                rst.add(null);
            } else {
                rst.add(String.valueOf(curr.left.value));
                queue.add(curr.left);
            }

            if (curr.right == null) {
                rst.add(null);
            } else {
                rst.add(String.valueOf(curr.right.value));
                queue.add(curr.right);
            }
        }

        return rst;
    }
	
    // 层序遍历反序列化
    public static Node levelBuild(Queue<String> serial) {
        if (serial == null || serial.isEmpty()) return null;

        Queue<Node> queue = new LinkedList<>();

        String rootValue = serial.poll();
        if (rootValue == null) {
            return null;
        }

        Node root = new Node(Integer.parseInt(rootValue));
        queue.add(root);

        while (!queue.isEmpty()) {
            Node parent = queue.poll();
            String left = serial.poll();
            String right = serial.poll();

            if (left != null) {
                Node leftChild = new Node(Integer.parseInt(left));
                queue.add(leftChild);
                parent.left = leftChild;
            }

            if (right != null) {
                Node rightChild = new Node(Integer.parseInt(right));
                queue.add(rightChild);
                parent.right = rightChild;
            }
        }

        return root;
    }
}

3. N叉树编码为二叉树 (LeetCode 431)

N叉树（N-ary Tree）的节点可以有多个孩子（一个List<Node>），而二叉树节点最多只有左右两个孩子。编码（Encode）是指将N叉树转换为二叉树，解码（Decode）则是逆过程。

3.1 核心思路

编码的核心思想是建立一种“左孩子-右兄弟”的表示法。

编码 (N叉树 -> 二叉树)：
1. N叉树的根节点（root）对应二叉树的根节点（head）。
2. N叉树根节点的所有孩子节点列表（root.children），被编码为二叉树根节点的左子树（head.left）。
3. 具体来说，N叉树的第一个孩子成为二叉树的左孩子（head.left）。 N叉树的第二个孩子成为二叉树左孩子的右兄弟（head.left.right），第三个孩子成为第二个孩子的右兄弟（head.left.right.right），以此类推。
4. 这个过程递归地应用于所有节点（即N叉树的每个孩子的子列表，都成为其对应二叉树节点的左子树）。
解码 (二叉树 -> N叉树)：

反序列化是上述过程的逆操作。
1. 二叉树的根节点（root）对应N叉树的根节点（head）。
2. 二叉树根节点的左孩子（root.left）及其所有右兄弟（root.left.right, ...）被解码为N叉树根节点的孩子列表。
3. 我们遍历这个“右兄弟链表”（while (root != null)），对每个节点递归调用解码函数（deCodeChild(root.left)）来处理它自己的孩子（存储在它的left指针上），并将结果加入N叉树的孩子列表。

3.2 Java实现

java

package L11;

import java.util.ArrayList;
import java.util.List;

public class SerializeNaryTree {

    public static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static TreeNode encodeNaryToBT(Node root) {
        if (root == null) return null;

        TreeNode head = new TreeNode(root.val);

        int count = 0;
        TreeNode curr = head;
        for (Node item : root.children) {
            if (count == 0) {
                curr.left = encodeNaryToBT(item);
                curr = curr.left;
                count++;
            } else {
                curr.right = encodeNaryToBT(item);
                curr = curr.right;
            }
        }

        return head;
    }

    public static TreeNode enCode(Node root) {
        if (root == null) return null;

        TreeNode head = new TreeNode(root.val);
        head.left = enCodeChild(root.children);

        return head;
    }

    private static TreeNode enCodeChild(List<Node> children) {
        if (children == null || children.isEmpty()) return null;

        TreeNode head = null;
        TreeNode curr = null;

        for (Node child : children) {
            if (head == null) {
                head = new TreeNode(child.val);
                curr = head;
            } else {
                curr.right = new TreeNode(child.val);
                curr = curr.right;
            }
            curr.left = enCodeChild(child.children);
        }

        return head;
    }

    public static Node deCode(TreeNode root) {
        if (root == null) return null;
        Node head = new Node(root.val, deCodeChild(root.left));

        return head;
    }

    private static List<Node> deCodeChild(TreeNode root) {
        List<Node> children = new ArrayList<>();

        while (root != null) {
            Node curr = new Node(root.val, deCodeChild(root.left));
            root = root.right;
            children.add(curr);
        }

        return children;
    }
}

4. 求二叉树最大宽度

二叉树的最大宽度是指在所有层中，节点数最多的一层包含的节点数。

4.1 核心思路

这个问题可以使用层序遍历来解决，关键在于如何标记每一层的结束。我们可以使用两个变量来实现：

currTail：指向当前层（正在遍历的层）的最末尾节点。
nextTail：指向下一层的最末尾节点。

实现步骤：

初始化队列，将根节点入队。currTail初始化为根节点。
使用一个计数器 leveCount 来记录当前层的节点数，max 记录全局最大宽度。
开始层序遍历（从队列弹出节点poll）：
- leveCount 加 1。
- 当左孩子入队时，更新 nextTail = poll.left。
- 当右孩子入队时，更新 nextTail = poll.right。 (由于右孩子总在左孩子之后入队，nextTail总能被正确更新为该层最后一个入队的节点)。
当弹出的节点 poll 正好是 currTail 时，说明当前层已经遍历完毕。
此时，比较 leveCount 和 max 并更新最大值。
重置 leveCount = 0，并将 currTail 更新为 nextTail（即下一层的末尾节点），准备开始下一层的遍历。

4.2 Java实现

java

package L11;

import java.util.LinkedList;
import java.util.Queue;

public class TreeMaxWidth {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static int getMaxWidth(Node root) {
        if (root == null) return 0;

        Queue<Node> queue = new LinkedList<>();
        Node currTail = root;
        Node nextTail = null;
        int max = Integer.MIN_VALUE;

        queue.add(root);
        int leveCount = 0;
        while(!queue.isEmpty()) {
            Node poll = queue.poll();
            leveCount++;

            if (poll.left != null) {
                queue.add(poll.left);
                nextTail = poll.left;
            }
            if (poll.right != null) {
                queue.add(poll.right);
                nextTail = poll.right;
            }

            if (poll == currTail) {
                max = Math.max(max, leveCount);
                leveCount = 0;
                currTail = nextTail;
            }
        }

        return max;
    }

}

5. 求后继结点

后继节点（Successor Node）是指在一棵二叉树的中序遍历（左 -> 根 -> 右）序列中，一个节点的下一个节点。

（注意：此问题的前提是节点定义中包含一个指向父节点的parent指针。）

5.1 核心思路

根据中序遍历的定义，寻找一个节点的后继者可以分为两种情况：

情况一：当前节点（curr）存在右子树。
- 根据中序遍历（左->根->右），访问完curr后，下一个访问的节点必然是其右子树中“最左”的那个节点。
- 即从 curr.right 开始，一直向左遍历到底（while (rst.left != null)）。
情况二：当前节点没有右子树。
- 这意味着以该节点为根的子树已经访问完毕。我们需要向上回溯，寻找一个“祖先”节点，且当前节点（curr）位于这个“祖先”节点的左子树中。
- 我们沿着 parent 指针向上遍历。
- 如果当前节点 rst 是其父节点 rst.parent 的右孩子，说明父节点也已经被访问过（左-根-右），需要继续向上。
- 直到找到一个节点 rst，它是其父节点 rst.parent 的左孩子。此时，这个父节点 rst.parent 就是后继者。
如果向上遍历到根节点（parent == null）都未找到（即当前节点是整棵树的最右节点），说明当前节点是中序遍历的最后一个节点，它没有后继者，返回null。

5.2 Java实现

java

package L11;

public class TreeNodeSuccessor {

    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getSuccessorNode(Node curr) {

        Node rst = null;
        if (curr.right != null) {
            rst = curr.right;
            while (rst.left != null) {
                rst = rst.left;
            }
            return rst;
        } else {
            rst = curr;
            while (rst.parent != null) {
                if (rst.parent.left == rst) {
                    return rst.parent;
                }
                rst = rst.parent;
            }
        }

        return null;
    }

}

6. 折纸问题

6.1 问题描述

将一段纸条从下往上对折N次，展开后，从上到下打印所有折痕的方向（“凹”或“凸”）。

N=1时：1条折痕，凹 (down)
N=2时：3条折痕，从上到下为：凹、凹、凸 (down, down, up) （注：代码注释中"N=2时，打印: up"有误，"下折痕、下折痕和上折痕"是正确的。）

6.2 核心思路

这个问题可以通过观察规律，将其转换为一个二叉树的中序遍历问题。

我们可以构建一个“概念上”的二叉树。
第一次折叠（N=1），产生一条“凹”折痕，我们将它作为树的根节点。
每进行一次新的折叠，都会在所有已存在的折痕上，派生出两条新折痕。
在我们的二叉树模型中，我们规定：所有新产生的左孩子都是“凹”折痕，所有新产生的右孩子都是“凸”折痕。
N=2时的树如下（在N=1的"凹"根节点上，新增了左孩子"凹"和右孩子"凸"）：
plaintext
```
      凹 (第1次)
     /   \
   凹 (第2次) 凸 (第2次)
```

N=3时，N=2时的所有节点都会产生新的左右孩子：

plaintext

通过观察物理折叠顺序，"从上到下"打印所有折痕，恰好对应了这棵概念二叉树的中序遍历（左 -> 根 -> 右）。

6.3 Java实现

我们使用一个递归函数 process(i, n, down) 来模拟中序遍历。

i：代表当前节点的层数。
n：代表总折叠次数（即树的最大深度）。
down：布尔值，true 代表“凹”，false 代表“凸”。

递归逻辑如下：

如果 i > n，说明已超过最大深度，返回。
递归调用 process(i + 1, n, true)（遍历左子树，固定为“凹”）。
打印当前节点（根据 down 变量打印“凹”或“凸”）。
递归调用 process(i + 1, n, false)（遍历右子树，固定为“凸”）。

java

public class PaperFoldingProblem {

    public static void printFolds(int n) {
        process(1, n, true);
        System.out.println();
    }

    public static void process(int i, int n, boolean down) {
        if (i > n) return;

        process(i + 1, n, true);
        System.out.print(down ? "凹" : "凸");
        process(i + 1, n, false);

    }
}