在不使用全局变量的情况下，使用按/前/后顺序递归的方法按正确顺序返回树节点列表

Question

当使用递归方法按in/pre/post顺序遍历时，我目前正在尝试为二叉树获得正确的节点排序。我能够使用的唯一解决方案是使用一个全局变量来保存每种遍历类型的列表。我想找到一种方法来获得我得到的结果，而不需要为排序列表使用全局变量。

这是我的代码：

class Node: 
def __init__(self,key,left,right): 
self.left = left
self.right = right
self.val = key 
#GLOBAL VARIABLES
inList = []
preList = []
postList = []
#NO GLOBAL VARIABLE USED HERE
def inorder(root): 
if root: 
inorder(root.left) 
print(root.val), 
inorder(root.right) 
def postorder(root): 
if root: 
postorder(root.left) 
postorder(root.right) 
postList.append(root.val) 
return postList
def preorder(root):
if root: 
preList.append(root.val) 
preorder(root.left)  
preorder(root.right)
return preList
def testCase(testNumber, function, root, expectedAnswer):
if expectedAnswer==function(root):
print "Test", testNumber, "passed."
else:
print "Test", testNumber, "failed."
def test1():
f = Node("f", [], [])
c = Node("c", f, [])
e = Node("e", [], [])
g = Node("g", [], [])
d = Node("d", [], g)
b = Node("b", d, e)
root = Node("a", b, c)
testCase(1, inorder, root, ['d', 'g', 'b', 'e', 'a', 'f', 'c'])
testCase(2, preorder, root, ['a', 'b', 'd', 'g', 'e', 'c', 'f'])
testCase(3, postorder, root, ['g', 'd', 'e', 'b', 'f', 'c', 'a'])
testCase(4, inorder, c, ['f','c'])
testCase(5, preorder, e, ['e'])

Answer 1

您可以使用有序遍历并返回当前子树的排序列表，并像left_subtree_result+[current_node]+right_subtree-result这样递归地连接它们。在这种情况下，链表会提供更好的性能，因为join是O(1(。(我指的是连接(

代码将是

def inorder(node):
if node is None:
return []
return inorder(node.left) + [node] + inorder(node.right)

Answer 2

只需将要填写的列表传递给函数即可。您甚至不需要返回它，因为追加会在适当的位置修改列表。由于您的三次遍历几乎相同，我将重点讨论inorder:

添加一个额外的参数：

def inorder(root, inList):
if root: 
inorder(root.left, inList) 
inList.append(root.val)
inorder(root.right, inList)

一旦完成了所有三种方法的操作(包括删除return语句(，就可以更新testCase函数以传入本地列表：

def testCase(testNumber, function, root, expectedAnswer):
actualAnswer = []
function(root, actualAnswer)
if expectedAnswer == actualAnswer:
print "Test", testNumber, "passed."
else:
print "Test", testNumber, "failed."