二叉树的层次遍历

[ChuChencheng]

问题

LeetCode 102

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

返回其层次遍历结果：

[
[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) {
    const result = []
    if (!root) return result
    const traverse = (node, depth) => {
        if (!result[depth]) result[depth] = []
        result[depth].push(node.val)
        if (node.left) traverse(node.left, depth + 1)
        if (node.right) traverse(node.right, depth + 1)
    }
    traverse(root, 0)
    return result
};

DFS

类似非递归求二叉树的深度的做法，在遍历同时记录当前层级的节点

/**
 * 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) {
    const result = []
    if (!root) return result
    const stack = [[root, 0]]
    while (stack.length) {
        const info = stack.pop()
        const node = info[0]
        const level = info[1]
        if (node) {
            if (!result[level]) result[level] = []
            result[level].push(node.val)
            stack.push([node.right, level + 1])
            stack.push([node.left, level + 1])
        }
    }
    return result
};

4

BFS

/**
 * 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) {
    const result = []
    if (!root) return result
    const queue = [[root, 0]]
    while (queue.length) {
        const info = queue.shift()
        const node = info[0]
        const level = info[1]
        if (node) {
            if (!result[level]) result[level] = []
            result[level].push(node.val)
            queue.push([node.left, level + 1])
            queue.push([node.right, level + 1])
        }
    }
    return result
};