算法题/树的BFS：二叉树的层序遍历

题目

给定一个二叉树，填充一个数组来表示它的逐级遍历。我们应该在单独的子数组中从左到右填充每个级别的所有节点的值。

解法

Java

import java.util.*;

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

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

class LevelOrderTraversal {
    public static List<List<Integer>> traverse(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null)
            return result;

        Queue<TreeNode> queue = new LinkedList<>();//用队列保存每一层的节点，临时存储
        queue.offer(root);//将根节点加入队列
        //外层循环；如果队列不为空，则进行后序操作
        while (!queue.isEmpty()) {
            int levelSize = queue.size();//当前层的元素个数，用于控制每次遍历队列中的元素个数
            List<Integer> currentLevel = new ArrayList<>(levelSize);//保存当前层的节点
            //内层循环；每次遍历队列中的节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                //将当前遍历到的元素添加到arrayList中保存
                currentLevel.add(currentNode.val);
                //同时将遍历到的节点的子节点添加到队列中
                if (currentNode.left != null)
                    queue.offer(currentNode.left);
                if (currentNode.right != null)
                    queue.offer(currentNode.right);
            }
            result.add(currentLevel);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(12);
        root.left = new TreeNode(7);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(9);
        root.right.left = new TreeNode(10);
        root.right.right = new TreeNode(5);
        List<List<Integer>> result = LevelOrderTraversal.traverse(root);
        System.out.println("Level order traversal: " + result);
    }
}

JavaScript

class TreeNode {
    constructor(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    }
}

class LevelOrderTraversal {
    static traverse(root) {
        const result = [];
        if (root === null)
            return result;

        const queue = [];
        queue.push(root);
        
        while (queue.length > 0) {
            const levelSize = queue.length;
            const currentLevel = [];
            
            for (let i = 0; i < levelSize; i++) {
                const currentNode = queue.shift();
                currentLevel.push(currentNode.val);
                
                if (currentNode.left !== null)
                    queue.push(currentNode.left);
                
                if (currentNode.right !== null)
                    queue.push(currentNode.right);
            }
            
            result.push(currentLevel);
        }
        
        return result;
    }
}

const root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(9);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);

const result = LevelOrderTraversal.traverse(root);
console.log("Level order traversal: " + JSON.stringify(result));

Python

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class LevelOrderTraversal:
    def traverse(root):
        result = []
        if root is None:
            return result

        queue = deque()
        queue.append(root)

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                current_node = queue.popleft()
                current_level.append(current_node.val)

                if current_node.left:
                    queue.append(current_node.left)

                if current_node.right:
                    queue.append(current_node.right)

            result.append(current_level)

        return result

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(9)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)

result = LevelOrderTraversal.traverse(root)
print("Level order traversal:", result)

Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type LevelOrderTraversal struct{}

func (lot *LevelOrderTraversal) traverse(root *TreeNode) [][]int {
	result := [][]int{}
	if root == nil {
		return result
	}

	queue := []*TreeNode{root}

	for len(queue) > 0 {
		levelSize := len(queue)
		currentLevel := []int{}

		for i := 0; i < levelSize; i++ {
			currentNode := queue[0]
			queue = queue[1:]

			currentLevel = append(currentLevel, currentNode.Val)

			if currentNode.Left != nil {
				queue = append(queue, currentNode.Left)
			}

			if currentNode.Right != nil {
				queue = append(queue, currentNode.Right)
			}
		}

		result = append(result, currentLevel)
	}

	return result
}

func main() {
	root := &TreeNode{Val: 12}
	root.Left = &TreeNode{Val: 7}
	root.Right = &TreeNode{Val: 1}
	root.Left.Left = &TreeNode{Val: 9}
	root.Right.Left = &TreeNode{Val: 10}
	root.Right.Right = &TreeNode{Val: 5}

	lot := &LevelOrderTraversal{}
	result := lot.traverse(root)
	fmt.Println("Level order traversal:", result)
}