Inorder二进制树遍历(使用Python)

Question

我正在尝试对树执行有序遍历。代码本身感觉是正确的，只是工作不正常。我有一种感觉，它要么和if条件有关，要么和append在python中的工作方式有关，要么可能和return有关。我认为，如果我使用打印而不是返回，这是正确的，但我希望能够使用返回并仍然得到正确的答案。例如，对于树[1，None，2,3]，我的代码返回[1]，这显然是不正确的。

此外，是否可以使用列表理解来解决这个问题？如果是这样的话，任何示例代码都将不胜感激。

这是我的代码：

class Solution(object):
def inorderTraversal(self, root):
res = []
if root:
self.inorderTraversal(root.left)
res.append(root.val)
self.inorderTraversal(root.right)
return res

同样在将其标记为重复之前，我知道Stackoverflow上已经要求按顺序遍历(很多次)，但都没有帮助我理解为什么我的理解是错误的。如果有人帮我学会如何纠正我的做法，而不是简单地发布另一个没有解释的链接，我将不胜感激。非常感谢！

Answer 1

这不起作用的原因是res只附加了您赋予它的第一个节点的值；每次递归调用函数时，它只会生成一个新的res.不过这是一个简单的修复方法，如下所示：

class Solution(object):
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left) 
res.append(root.val)
res = res + self.inorderTraversal(root.right)
return res

在这种情况下，它返回左分支、值，然后返回右分支。这可以更简单地完成，如下所示：

class Solution(object):
def inorderTraversal(self, root):
return (self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)) if root else []

Answer 2

使用这个，一个简单的递归：：

class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
def printInorder(root):
if root:
printInorder(root.left)
print(root.val)
printInorder(root.right)
def printPostorder(root):
if root:
printPostorder(root.left)
printPostorder(root.right)
print(root.val)
def printPreorder(root):
if root:
print(root.val)
printPreorder(root.left)
printPreorder(root.right)
# Driver code
root = Node(1)
root.left      = Node(2)
root.right     = Node(3)
root.left.left  = Node(4)
root.left.right  = Node(5)
print "Preorder traversal of binary tree is"
printPreorder(root)
print "nInorder traversal of binary tree is"
printInorder(root)
print "nPostorder traversal of binary tree is"
printPostorder(root)

来源：：此处

Answer 3

@Benedict Randall Shaw的答案已经很完美了。我只是想以蟒蛇的方式给它增添一些乐趣。尽管文档不建议使用可变对象作为默认参数，但通过将默认可变list视为python函数的类成员，这将在一定程度上简化代码。

不同的是，只有+=被=取代，因为在函数对象被垃圾收集之前，res始终是函数内的同一个list对象。

def inorderTraversal(root, res=[]):
if root:
res = inorderTraversal(root.left)
res.append(root.val)
res = inorderTraversal(root.right)
return res

Answer 4

还有一种输出列表的方法，其优点是只需要向单个列表添加值：

def inorder(root):
return_list = []
def innerInOrder(root):
if root == None:
return
innnerInOrder(root.left)
return_list.append(root.data)
innerInOrder(root.right)
innerInOrder(root)
return return_list

Answer 5

您可以在函数外部声明列表，这样它就不会在每次调用函数时创建新的列表(因为它是递归函数)，但您可以使用其他发布的方法。：-)