算法题练习——JS Node+python题解NC15 求二叉树的层序遍历

柔光的暖阳◎ 2024-04-07 11:11 63阅读 0赞

**描述**

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

> 例如：  
> 给定的二叉树是\{3,9,20,\#,\#,15,7\},  
> ![5c339a469a8944b296932ab005cc694f.png][]  
> 该二叉树层序遍历的结果是  
> \[\[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<len; 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

[5c339a469a8944b296932ab005cc694f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2cd24dc8406e47059717a194dfd77d2c.png