的Python：二叉搜索树和递归返回一个嵌套列表

Question

鉴于二叉搜索树，例如：

 9 
      8 
    7 
5 
    3 
     2 

我想获得节点的有序列表A和B之间的值（含）。

我实现了一个递归辅助函数：

def _range(root, a, b): 
node_list = [] 
if root.left: 
    node_list.append(_range(root.left, a, b)) 
if root.value >= a and root.value <= b: 
    node_list.append(root) 
if root.right: 
    node_list.append(_range(root.right, a, b)) 
return node_list 

这给了我：

[[[BTNode: 2], BTNode: 3], BTNode: 5, [BTNode: 7, [[BTNode: 8], BTNode: 9]]] 

不过，我需要：

[BTNode: 2, BTNode: 3, BTNode: 5, BTNode: 7, BTNode: 8, BTNode: 9] 

反正是有压平列表？我意识到我正在做的是将列表附加到另一个列表，但不知道如何解决这个问题而不破坏代码。

Answer 1

append将您作为参数传递给的对象添加到列表中，所以显然最终会生成嵌套列表。要连接的结果，所以要使用list.extend（或+=运营商）：

>>> from collections import namedtuple 
>>> class Node(namedtuple('Node', 'value left right')): 
...  # I reimplement __str__ just to avoid too much output later 
...  def __repr__(self): 
...    return 'Node(%r)' % self.value 
...  __str__ = __repr__ 
... 
>>> def make_node(value, left=None, right=None): 
...  return Node(value, left, right) 
... 
>>> def _range(root, a, b): 
...  node_list = [] 
...  if root.left: 
...    node_list.extend(_range(root.left, a, b)) 
...  if a <= root.value <= b: 
...    node_list.append(root) 
...  if root.right: 
...    node_list.extend(_range(root.right, a, b)) 
...  return node_list 
... 
>>> tree = make_node(5, make_node(3, make_node(2)), make_node(7, None, make_node(8, None, make_node(9)))) 
>>> _range(tree, 1, 3) 
[Node(2), Node(3)] 
>>> _range(tree, 1, 10) 
[Node(2), Node(3), Node(5), Node(7), Node(8), Node(9)] 

做这将是通过周围列表作为参数的其他方式：

>>> def _range(root, a, b, node_list=None): 
...  if node_list is None: 
...    # Note: do *not* use "[]" as a default! 
...    node_list = [] 
...  if root.left: 
...    _range(root.left, a, b, node_list) 
...  if a <= root.value <= b: 
...    node_list.append(root) 
...  if root.right: 
...    _range(root.right, a, b, node_list) 
...  return node_list 
... 
>>> _range(tree, 1, 3) 
[Node(2), Node(3)] 
>>> _range(tree, 1, 10) 
[Node(2), Node(3), Node(5), Node(7), Node(8), Node(9)]