Java 链表实现二叉树

在 Java 中，我们可以使用链表来实现二叉树。具体实现方法如下：

首先，我们需要定义一个二叉树的节点类：

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

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

然后，我们定义一个链表节点类，该类包含一个指向二叉树节点的指针和一个指向下一个链表节点的指针：

class ListNode {
    TreeNode node;
    ListNode next;

    public ListNode(TreeNode node) {
        this.node = node;
        this.next = null;
    }
}

接下来，我们定义一个链表类，该类包含一个指向链表头节点的指针：

class LinkedList {
    ListNode head;

    public LinkedList() {
        this.head = null;
    }

    public void add(TreeNode node) {
        ListNode newNode = new ListNode(node);
        if (head == null) {
            head = newNode;
        } else {
            ListNode curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }

    public boolean isEmpty() {
        return head == null;
    }

    public TreeNode remove() {
        if (head == null) {
            return null;
        } else {
            TreeNode node = head.node;
            head = head.next;
            return node;
        }
    }
}

最后，我们使用链表来实现二叉树的层次遍历：

public static void levelOrderTraversal(TreeNode root) {
    LinkedList queue = new LinkedList();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.remove();
        System.out.print(node.val + " ");
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

这样，我们就使用链表成功地实现了二叉树的层次遍历。