二叉树层序遍历算法实现

二叉树层序遍历算法实现

二叉树层序遍历算法实现

• 1. 二叉树的定义
• 2. 层序遍历实现
• 3. 复杂度分析
• 4. 总结

1. 二叉树的定义

代码如下（java 语言实现）：

// Definition for a binary tree node.
public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}

2. 层序遍历实现

要进行层序遍历，需要借助一个队列。先将二叉树根节点入队，然后出队，访问出队结点。若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根节点入队。然后出队，访问出队结点。如此反复，直到队列为空。

代码如下（Java 语言实现）：

public List> levelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    // 队列存放同一层的结点
    Queue dq = new linkedList<>(); 
    // 以每一层的结点值为一个 List,将所有层放入一个大的 List
    List> resList = new ArrayList<>();
    dq.offer(root);
    while (!dq.isEmpty()) {
        int size = dq.size();
        // 将同层结点值放入 List 中
        List res = new ArrayList<>();
        while (size > 0) {
            TreeNode node = dq.poll();
            if (node.left != null) dq.offer(node.left);
            if (node.right != null) dq.offer(node.right);
            res.add(node.val);
            size--;
        }
        resList.add(res);
    }
    return resList;
}

3. 复杂度分析

记树上所有节点的个数为 n.
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n).
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n).

4. 总结

二叉树的层序遍历算法的代码实现，可以作为一个模板，将来用于解决于层序遍历相关的任何问题，一定要熟记于心！