中序遍历二叉树（使用Python）

Question

我正在尝试对一棵树执行中序遍历。代码本身感觉没问题，但它没有正常工作。我有一种感觉，这可能与if条件、python中的append工作方式或者返回值等有关。如果我使用print而不是return，这个代码可以正确运行，但我想能够使用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上已经问过许多次关于顺序遍历的问题，但是它们都没有帮助我理解为什么我的理解是错误的。如果有人可以帮助我学习如何纠正我的方法而不仅仅是发布另一个链接而没有解释，我将非常感激。非常感谢！

- Jane Sully

---

树的结构是怎样的？ - Patrick Haugh

这是一棵二叉树（不一定是二叉搜索树）。例如，传入根节点的列表格式为根节点、左子树、右子树……[1, None, 2, 3] 的根节点为 1，没有左孩子，右孩子为 2（它有一个左孩子为 3）。 - Jane Sully

我问这个问题的原因是因为你似乎在传递一个列表给 root，但是列表没有 left 或 right 属性。 - Patrick Haugh

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 []

- Benedict Randall Shaw

---

非常感谢！这很有道理。 - Jane Sully

每次调用inorderTraversal函数时，由于在函数中首先执行的操作是将结果列表重置为空字符串，因此您的结果列表不会保留之前的值。 - Nicholas Johnson

@NicholasJohnson 不会；每次调用 inorderTraversal 都包含其自己独立的 res 实例，该实例对于该调用是唯一的。 - Benedict Randall Shaw

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)

Source :: here

- Akash Kandpal

Answer 3

@Benedict Randall Shaw的回答已经很完美了。我只想以一种Pythonic的方式增添一些乐趣。虽然doc不建议使用可变对象作为默认参数，但这将通过将默认可变的list视为Python函数的类成员而使代码变得更加简单。

唯一的区别是将+=替换为=，因为在函数对象被垃圾收集之前，res始终是函数内部相同的list对象。

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

- Yossarian42

---

这种方法的问题在于列表'res'在函数'inorderTraversal()'的整个生命周期中都被维护。对该函数的多次调用将不断向'res'列表中添加内容。 - MLKing

Answer 4

你可以在函数外部声明列表，这样每次调用函数时就不会创建新的列表（因为它是一个递归函数），但你也可以使用其他方法。 :-)

- Abhinav Reddy

Answer 5

另一种输出列表的方法是，优点在于您只需要将值添加到单个列表中：

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

- okay