102.二叉树的层序遍历

链接：102.二叉树的层序遍历
难度：Medium
标签：树、广度优先搜索、二叉树
简介：给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

题解 1 - python

• 编辑时间：2024-02-14
• 执行用时：44ms
• 内存消耗：17.13MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque() 
        q.append(root)
        size = 1
        ans = [[root.val]]
        while q:
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            size -= 1
            if size == 0:
                size = len(q)
                if q: ans.append([node.val for node in q])
        return ans

题解 2 - c

• 编辑时间：2021-11-27
• 执行用时：8ms
• 内存消耗：7.3MB
• 编程语言：c
• 解法介绍：递归。

#define MAX 2000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int **arr = (int **)malloc(sizeof(int) * MAX);
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(sizeof(int) * MAX);
    if (!root) return arr;
    // 维护队列储存节点信息
    struct TreeNode *q[2000];
    q[0] = root;
    // 维护队列头尾指针
    int head = 0, tail = 1;
    // 维护当前层的元素数量，当前遍历的层级
    int size = 1, height = 1;
    arr[0] = (int *)malloc(sizeof(int));
    arr[0][0] = root->val;
    (*returnColumnSizes)[0] = 1;
    while (head != tail) {
        // 每次出队一个节点
        struct TreeNode *node = q[head++];
        // 若左节点不为空则入队
        if (node->left) q[tail++] = node->left;
        // 若右节点不为空则入队
        if (node->right) q[tail++] = node->right;
        // 若当前层无元素，说明队列里都是下一层的元素
        if (--size == 0) {
            size = tail - head;
            *returnSize += 1;
            (*returnColumnSizes)[height] = size;
            arr[height] = (int *)malloc(sizeof(int) * size);
            for(int i = head; i < tail; i++) arr[height][i - head] = q[i]->val;
            height++;
        }
    }
    return arr;
}

题解 3 - java

• 编辑时间：2020-02-21
• 执行用时：1ms
• 内存消耗：39.3MB
• 编程语言：java
• 解法介绍：递归。

class Solution {
   	LinkedList<List<Integer>> list = new LinkedList<List<Integer>>();
	public List<List<Integer>> levelOrder(TreeNode root) {
		if (root == null)
			return list;
		inLevelOrder(root,0);
		return list;
	}
	public void inLevelOrder(TreeNode node,int level){
		if(list.size()==level) {
			list.add(new ArrayList<Integer>());
		}
		list.get(level).add(node.val);
		if(node.left!=null)
		inLevelOrder(node.left, 1+level);
		if(node.right!=null)
		inLevelOrder(node.right, 1+level);
	}
}

题解 4 - javascript

• 编辑时间：2020-02-21
• 执行用时：72ms
• 内存消耗：34.8MB
• 编程语言：javascript
• 解法介绍：迭代。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (root === null) return [];
  const queue = [root];
  const res = [[root.val]];
  let size = 1;
  while (queue.length !== 0) {
    const node = queue.shift();
    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
    if (--size === 0) {
      if (queue.length !== 0) res.push(queue.map(node => node.val));
      size = queue.length;
    }
  }
  return res;
};

题解 5 - java

• 编辑时间：2020-02-21
• 执行用时：2ms
• 内存消耗：39.6MB
• 编程语言：java
• 解法介绍：迭代。

class Solution {
   	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> list = new LinkedList<List<Integer>>();
		if (root == null)
			return list;
		List<Integer> tmplist = new LinkedList<Integer>();
		int size=1;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			tmplist.add(node.val);
			if(node.left!=null)queue.offer(node.left);
			if(node.right!=null)queue.offer(node.right);
			size--;
			if(size==0) {
				size=queue.size();
				list.add(tmplist);
				tmplist=new LinkedList<Integer>();
			}
		}
		return list;
	}
}