中序二叉树遍历（使用 Python）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/41622174/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Inorder Binary Tree Traversal (using Python)
提问by Jane Sully
I am trying to perform an inorder traversal of a tree. The code itself feels right, except it is not working properly. I have a feeling it has to either do with the if condition, how append works in python, or something perhaps with return. This works correctly if I use print instead of return, I think, but I want to be able to use return and still get the correct answer. For example, for the tree [1,None,2,3], my code returns [1] which is clearly incorrect.
我正在尝试对树进行中序遍历。代码本身感觉是正确的，只是它不能正常工作。我有一种感觉，它要么与 if 条件有关，也与 append 在 python 中的工作方式有关，或者与返回有关。如果我使用打印而不是返回，这可以正常工作，我想，但我希望能够使用返回并仍然得到正确的答案。例如，对于树 [1,None,2,3]，我的代码返回 [1]，这显然是不正确的。
Additionally is it possible to solve this problem using list comprehension? If so, any sample code would be greatly appreciated.
另外是否可以使用列表理解来解决这个问题？如果是这样，任何示例代码将不胜感激。
Here is my code:
这是我的代码：
class Solution(object):
def inorderTraversal(self, root):
res = []
if root:
self.inorderTraversal(root.left)
res.append(root.val)
self.inorderTraversal(root.right)
return res
Also before marking this as a duplicate, I know in order traversals have been asked on Stackoverflow (plenty of times), but none of them helped me understand why my understanding is wrong. I would be so grateful if someone helped me learn how to correct my approach versus simply posting another link without explanation. Thank you so much!
同样在将其标记为重复之前，我知道在 Stackoverflow 上按顺序询问了遍历（很多次），但没有一个帮助我理解为什么我的理解是错误的。如果有人帮助我学习如何纠正我的方法，而不是简单地发布另一个链接而无需解释，我将不胜感激。非常感谢！
回答by Benedict Randall Shaw
The reason this doesn't work is that resonly has the value of the first node you give it appended to it; each time you recursively recall the function, it just makes a new res. It is a simple fix though, as follows:
这不起作用的原因是，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
In this, it returns the left branch, the value, and then the right. This can be done much more briefly as follows:
在这种情况下，它返回左分支，值，然后是右分支。这可以更简单地完成如下：
class Solution(object):
def inorderTraversal(self, root):
return (self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)) if root else []
回答by Akash Kandpal
Use this instead , a simple recursion ::
改用这个，一个简单的递归::
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)
Source :: here
来源：：这里
回答by Yossarian42
@Benedict Randall Shaw's answer is already perfect. I just want to add some fun to it in a pythonic way. Although the docdoes not suggest using a mutable object as default parameter, this will somewhat simplify the code by treating the default mutable listas a class member of the python function.
@Benedict Randall Shaw 的回答已经很完美了。我只是想以 Pythonic 的方式为它添加一些乐趣。尽管文档不建议使用可变对象作为默认参数，但通过将默认可变对象视为listpython 函数的类成员，这会在一定程度上简化代码。
The difference is only the +=is replaced by =, since the resis always the same listobject inside the function before the function object is garbage collected.
区别仅在于+=被 替换=，因为在函数对象被垃圾收集之前，res始终list是函数内部的相同对象。
def inorderTraversal(root, res=[]):
if root:
res = inorderTraversal(root.left)
res.append(root.val)
res = inorderTraversal(root.right)
return res
