Heading

102.二叉树的层序遍历 (opens new window)

Tags: algorithms amazon apple bloomberg facebook linkedin microsoft tree breadth-first-search

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Medium (63.54%)
• Likes: 674
• Dislikes: -
• Total Accepted: 209.3K
• Total Submissions: 329.1K
• Testcase Example: '[3,9,20,null,null,15,7]'

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

 

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

/*
 * @lc app=leetcode.cn id=102 lang=javascript
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * 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];
    let ret = [], n,
        p, tmp;
    while (queue.length) {
        tmp = []
        n = queue.length//队列总的元素个数恰好是当前层数的元素个数
        for (let i = 0; i < n; i++) {
            p = queue.shift();
            tmp.push(p.val);
            p.left && queue.push(p.left)
            p.right && queue.push(p.right)
        }
        ret.push(tmp);
    }
    return ret;
};
// @lc code=end