无队列的二叉树 BFS

Question

我正在研究 https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/ 的解决方案。

我想在不使用队列的情况下实现级别顺序遍历，因为该解决方案非常简单。

我写了下面的代码，理论上应该可以工作，但给出了错误的结果。我不知道为什么。

如有任何帮助，我们将不胜感激

class Node:
    # A utility function to create a new node
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None
        
def height(root):
    if root is None:
        return 0
    else:
        heightL = height(root.left)
        heightR = height(root.right)
        maxHeight = max(heightL, heightR)
        return maxHeight + 1
        
def nodesOnLevel(root, level, result=[]):
    if root is None:
        return result
    if level == 1:
        result.append(root.val)
    elif level > 1:
        nodesOnLevel(root.left, level-1, result)
        nodesOnLevel(root.right, level-1, result)
    return result
   
    
def levelOrder_noQueue(root):
    if root is None:
        return
    levels = height(root)
    results = []
    for i in range(1, levels+1):
        results.append(nodesOnLevel(root, i))
    return results;

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(levelOrder_noQueue(root))
# output is [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]
# desired output is [[1], [2,3], [4,5]]

Answer 1

问题出在result：您的代码中只有一个结果列表：

def nodesOnLevel(root, level, result=[]):

result 的默认值仅在 解析脚本时计算一次 ，而不是在调用函数时计算。这意味着当 levelOrder_noQueue 函数第二次调用此函数时（不传递第三个参数），result 将保持原样，第二次调用将继续使用它来附加更多元素。

因此将此代码更改为如下内容：

def nodesOnLevel(root, level, result=None):
    if result is None:
        result = []

或者，否则，不提供默认值，让调用者提供空列表：

def nodesOnLevel(root, level, result):

在levelOrder_noQueue中：

    results.append(nodesOnLevel(root, i, []))

无队列的二叉树 BFS

Binary Tree BFS without queue

python

binary-tree

breadth-first-search