Binary Tree Level Order Traversal - LeetCode

Binary Tree Level Order Traversal - LeetCode
タイトル:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example:Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

分析:
このテーマは幅優先検索を使用していますが、私は通常のBFSではありません.私は現在の層数を1つのマークで記録するだけで、それから直接広さ優先検索で行うことができます.結局、これは木で、本当の図ではありません.だから、広さは深さ検索より複雑です.
コード:

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def levelOrder(self, root):
        if not root:
            return []
        res = [[]]
        self.bfs(root,res,0)
        return res
    
    def bfs(self,root,l,i):
        if not root:
            return 
        if i == len(l):
            l.append([])
        l[i].append(root.val)
        self.bfs(root.left,l,i+1)
        self.bfs(root.right,l,i+1)

添付:
最後に他の人のコードを添付します.簡単なコードです.

def levelOrder(self, root):
    res,next=[],[]
    if root:
        temp=[root]
    else:
        return res
    res.append(temp)
    while 1:
        for v in temp:
            if v.left:
                next.append(v.left)                
            if v.right:
                next.append(v.right)
        if next==[]:
            break
        res.append(next)
        temp=list(next)
        next=[]
    return [[v.val for v in x] for x in res]