算法题练习——NC15 求二叉树的层序遍历、NC88 寻找第K大

描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[[3],[9,20],[15,7]]

数据范围：二叉树的节点数满足 1 \le n \le 10^5 \1≤n≤105 

示例1

输入：{1,2}

返回值：[[1],[2]]

示例2

输入：{1,2,3,4,#,#,5}

返回值：[[1],[2,3],[4,5]]

解析：

• 首先判断二叉树是否为空，空树没有遍历结果。
• 建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
• 每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
• 每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
• 访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。

JavaScript Node题解：

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
 
/**
  * 
  * @param root TreeNode类 
  * @return int整型二维数组
  */
function levelOrder( root ) {
    // write code here
    let res = []
    if(!root) return res
    let queue = []
    queue.push(root)
    while(queue.length){
        let temp = []
        let len = queue.length
        for(let i=0; i
            let node = queue.shift()
            temp.push(node.val)
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
        res.push(temp)
    }
    return res
}
module.exports = {
    levelOrder : levelOrder
};

python代码解：

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if not root: return None
        res = []
        queue = [root]
        while queue:
            res.append([node.val for node in queue])
            temp = []
            for node in queue:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
                queue = temp
        return res