Python中的二叉树层序遍历

Question

给定以下树：

我需要按照从左到右的顺序返回树的层序遍历： 因此，上面的示例将输出一个列表的列表：

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

我编写了以下代码，思路是递归地将节点值及其深度存储在队列中，然后迭代队列元组并将它们放入中间列表 O，如果没有相同深度的更多节点，则将 O 添加到输出并清空 O。但是我的代码超时了，有什么帮助吗？

import queue

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def helper(root,res,level):
            if not root:
                return res
            l=level+1
            res.put((root.val,level))
            helper(root.left,res,l)
            helper(root.right,res,l)

        res=queue.Queue()
        helper(root,res,0)

        d=1
        output=[]
        node,depth=res.get()
        output.append([node])
        while res:
            o=[]
            node,depth=res.get()
            while d ==depth:
                o.append(node)
                node,depth=res.get()
            else:
                d+=1
            output.append(o)    
            
        return output

- IS92

---

请修复您代码的格式。 - Michael Butscher

如果数字9有1或2个子节点，你能给出预期的输出吗？只是想确保你需要的是正确的前序遍历树还是BFS遍历。 - san

如果9有一个孩子说“6”，输出应该是[[3]，[9,20]，[6,15,7]]。 - IS92

@ElenaGT，好的，这是一个BFS。我刚刚在下面发布了解决方案作为答案。如果有帮助，请随意接受并投票。 :-) - san

Answer 1

下面是我的代码，用于实现广度优先搜索（BFS）迭代算法，将每个层级的节点都放在一个单独的列表中：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def BFS(self, root) -> int:
        level=1
        current=(root, level)
        s=set()
        result=[]
        Q = [current]
        while Q:
            current=Q.pop()
            level=current[1]
            if current[0] not in s:
                result.append([current[0].val, level])
                s.add(current[0])
            if current[0].left:
                Q.insert(0,(current[0].left, level+1))
            if current[0].right:
                Q.insert(0,(current[0].right, level+1))
        output=[]
        temp=[]
        level=1
        for val in result:
            if val[1]==level:
                temp.append(val[0])
            elif val[1] > level:
                output.append(temp)
                temp=[val[0]]
                level+=1
        output.append(temp)
        return output

测试：

n1=TreeNode(3)
n2=TreeNode(9)
n3=TreeNode(20)
n4=TreeNode(6)
n5=TreeNode(15)
n6=TreeNode(7)

n1.left=n2
n1.right=n3
n2.left=n4
n3.left=n5
n3.right=n6

sol1=Solution()
print(sol1.BFS(n1))
[[3], [9, 20], [6, 15, 7]]

- san

Answer 2

感谢 san 的答案。该解决方案帮助我解决了LeetCode的107问题。根据我的理解，我稍微修改了一下。解决这个问题有两种方法，但我更喜欢使用BFS方式。这个修改版在队列中压缩了值和级别。与仅打印树中每个节点的值相比，它提供了更多的灵活性，而其他教程则提供了这种方式。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]: 
        
        if root is None:
            return None
        
        level = 1
        q = []
        q.append((root,level)) # push both node and level.
        save = []
        
        while q:
            cur = q.pop(0)
            cur_node = cur[0]
            cur_level = cur[1]
            # print(cur_node.val)
            # print(cur_level)  
            save.append([cur_node.val, cur_level])
            if cur_node.left:
                q.append((cur_node.left, cur_level+1))
            if cur_node.right:
                q.append((cur_node.right, cur_level+1))
                
        print(save) # once print, you will have the idea about how to reorgnized the required output.
        level = 1
        output = []
        temp = []
        for i in range(len(save)):
            cur = save[i]
            #print(cur)
            if cur[1] == level:
                temp.append(cur[0])    
            if cur[1] != level:
                output.insert(0, temp)
                temp = []
                temp.append(cur[0])
                level = level + 1
            if i == len(save)-1:
                    output.insert(0, temp)
            
        return output

- Wennan Chang

Answer 3

您可以使用以下逻辑来按BFS打印节点。 如果您还需要，也可以修改该方法以返回一个列表。

def levelOrder(root):
qroot = []
print(root.info,end=' ')
if root.left:
    qroot.append(root.left)
if root.right:
    qroot.append(root.right)

while(qroot):
    tmp = qroot[0]
    if tmp.left:
        qroot.append(tmp.left)
    if tmp.right:
        qroot.append(tmp.right)

    print (tmp.info,end=' ')
    qroot.pop(0)

return

不必打印这些值，你可以直接将它们添加到一个新的列表中并返回同样的列表。

- Arya A.

---

你能否澄清一下这段代码是否旨在解决原始任务？我发现即使修复了格式问题（缩进等），这段代码仍然会陷入无限循环。我也不认为它按照OP所需的顺序跟踪级别。很抱歉指出这么多问题，但希望能有所帮助 :) - Aaron Bell