inorder木のトラバーサル

Question

私はツリー実装のinorder再帰的なトラバーサルを見ていて、どのように結果をリストに保存して、それを再帰関数から戻すことができるのだろうと思っています。スタックの巻き戻し中にこのリストを保持する方法に関する問題があります。

だから、私のようにコードを持っている：

class BinaryTreeNode(object): 
    def __init__(self, value): 
     self.value = value 
     self.left = None 
     self.right = None 

def recursive_inorder(root): 
    if not root: 
     return 

    nodes = list() 

    recursive_inorder(root.left) 
    nodes.append(root.value) 
    print root.value 
    recursive_inorder(root.right) 
    return nodes 

そして、私はこれを呼び出す：ノードが正しい順序で横断しているが、私はトラブル保存する方法を考え出すを持っています

three = BinaryTreeNode(3) 
five = BinaryTreeNode(5) 
one = BinaryTreeNode(1) 
four = BinaryTreeNode(4) 
two = BinaryTreeNode(2) 
six = BinaryTreeNode(6) 

three.left = five 
five.left = one 
five.right = four 

three.right = two 
two.left = six 

nodes = recursive_inorder(three) 

結果はnodesリストに表示されます。

Answer 1

再帰呼び出しの戻り値を使用して、ノードリストを拡張します。あなたがNone値を持っているときにも、あなたの関数は常にリストを返すことが保証されるように、空のリストを返す：

def recursive_inorder(root): 
    if not root: 
     return [] 

    nodes = list() 

    nodes.extend(recursive_inorder(root.left)) 
    nodes.append(root.value) 
    nodes.extend(recursive_inorder(root.right)) 
    return nodes 

それとももう少し簡潔：

def recursive_inorder(root): 
    if not root: 
     return [] 

    return recursive_inorder(root.left) + [root.value] + recursive_inorder(root.right)