算法题练习——JS Node+python题解NC14 按之字形顺序打印二叉树

秒速五厘米 2024-04-07 14:35 97阅读 0赞

**描述**

> 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

> 数据范围：0≤n≤1500,树上每个节点的val满足 ∣val∣<=1500  
> 要求：空间复杂度：O(n)，时间复杂度：O(n)

> 例如：  
> 给定的二叉树是\{1,2,3,\#,\#,4,5\}

![bdfff12791a84f8c8ecf89f16c9ef16b.png][]

>   
> 该二叉树之字形层序遍历的结果是
> 
> \[
> 
> \[1\],
> 
> \[3,2\],
> 
> \[4,5\]
> 
> \]

**示例1**

> 输入：\{1,2,3,\#,\#,4,5\}
> 
> 返回值：\[\[1\],\[3,2\],\[4,5\]\]
> 
> 说明：如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

**示例2**

> 输入：\{8,6,10,5,7,9,11\}
> 
> 返回值：\[\[8\],\[10,6\],\[5,7,9,11\]\]

**示例3**

> 输入：\{1,2,3,4,5\}
> 
> 返回值：\[\[1\],\[3,2\],\[4,5\]\]

**JavaScript题解：**

/* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function Print(pRoot)
    {
        // write code here
        if(!pRoot) return []
        let arr = []
        let tempArr = []
        tempArr.push(pRoot)
        let key = 0
        while(tempArr.length!=0){
            let arrList = []
            let len = tempArr.length
            while(len){
                let node = tempArr.shift()
                arrList.push(node.val)
                if(node.left){tempArr.push(node.left)}
                if(node.right){tempArr.push(node.right)}
                len--
            }
            key++
            if(key%2==1){
                arr.push(arrList)
            }else{
                arrList.reverse()
                arr.push(arrList)
            }
        }
        return arr
    }
    module.exports = {
        Print : Print
    };

**Python题解：**

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param pRoot TreeNode类 
    # @return int整型二维数组
    #
    class Solution:
        def Print(self , pRoot: TreeNode) -> List[List[int]]:
            # write code here
            if pRoot == None:
                return []
            arr = []
            tempArr = [pRoot]
            key = 0
            while tempArr:
                arrList = []
                childList = []
                for i in tempArr:
                    arrList.append(i.val)
                    if i.left:
                        childList.append(i.left)
                    if i.right:
                        childList.append(i.right)
                key += 1
                if key%2==1:
                    arr.append(arrList)
                else:
                    arrList.reverse()
                    arr.append(arrList)
                tempArr = childList
            return arr

[bdfff12791a84f8c8ecf89f16c9ef16b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f3b3a8cff9414d2f82b4a2752bf488cf.png