java二叉树层序遍历怎么实现

46次阅读

共计 888 个字符，预计需要花费 3 分钟才能阅读完成。

在 Java 中，可以使用队列来实现二叉树的层序遍历。具体步骤如下：

首先创建一个队列，将根节点入队。
进入循环，直到队列为空为止。在循环中，首先记录当前队列的大小，表示当前层的节点个数。
遍历当前层的节点个数次，每次将队头节点出队，并将其值存入结果列表中。同时，将其左右子节点入队。
将结果列表返回即可完成二叉树的层序遍历。

以下是 Java 代码示例：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

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

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

public class BinaryTreeLevelOrderTraversal {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();
        if (root == null) {return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) {queue.offer(node.left);
                }
                if (node.right != null) {queue.offer(node.right);
                }
            }

            result.add(level);
        }

        return result;
    }
}