Skip to content

Latest commit

 

History

History
129 lines (109 loc) · 2.67 KB

102.binary-tree-level-order-traversal.md

File metadata and controls

129 lines (109 loc) · 2.67 KB

题目地址

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

题目描述

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

思路

这道题可以借助队列实现,首先把root入队,然后入队一个特殊元素Null(来表示每层的结束)。

然后就是while(queue.length), 每次处理一个节点,都将其子节点(在这里是left和right)放到队列中。

然后不断的出队, 如果出队的是null,则表式这一层已经结束了,我们就继续push一个null。

关键点解析

  • 队列

  • 队列中用Null(一个特殊元素)来划分每层

  • 树的基本操作- 遍历 - 层次遍历(BFS)

  • 注意塞入null的时候,判断一下当前队列是否为空,不然会无限循环

代码

/*
 * @lc app=leetcode id=102 lang=javascript
 *
 * [102] Binary Tree Level Order Traversal
 *
 * https://leetcode.com/problems/binary-tree-level-order-traversal/description/
 *
 * algorithms
 * Medium (47.18%)
 * Total Accepted:    346.4K
 * Total Submissions: 731.3K
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * Given a binary tree, return the level order traversal of its nodes' values.
 * (ie, from left to right, level by level).
 *
 *
 * For example:
 * Given binary tree [3,9,20,null,null,15,7],
 *
 *
 * ⁠   3
 * ⁠  / \
 * ⁠ 9  20
 * ⁠   /  \
 * ⁠  15   7
 *
 *
 *
 * return its level order traversal as:
 *
 * [
 * ⁠ [3],
 * ⁠ [9,20],
 * ⁠ [15,7]
 * ]
 *
 *
 */
/**
 * 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) return [];
  const items = []; // 存放所有节点
  const queue = [root, null]; // null 简化操作
  let levelNodes = []; // 存放每一层的节点

  while (queue.length > 0) {
    const t = queue.shift();

    if (t) {
      levelNodes.push(t.val)
      if (t.left) {
        queue.push(t.left);
      }
      if (t.right) {
        queue.push(t.right);
      }
    } else { // 一层已经遍历完了
      items.push(levelNodes);
      levelNodes = [];
      if (queue.length > 0) {
        queue.push(null)
      }
    }
  }

  return items;
};

相关题目