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

Question

我正在尝试执行树的中序遍历。代码本身感觉不错，只是它不能正常工作。我感觉它要么与 if 条件有关，要么与 append 在 python 中的工作方式有关，或者可能与 return 有关。我认为，如果我使用 print 而不是 return，这将正常工作，但我希望能够使用 return 并仍然得到正确答案。例如，对于树 [1,None,2,3]，我的代码 returns [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

此外，在将其标记为重复之前，我知道在 Whosebug 上已经询问过顺序遍历（很多次），但其中 none 帮助我理解了为什么我的理解是错误的。如果有人帮助我学习如何纠正我的方法而不是简单地发布另一个 link 而不加解释，我将不胜感激。非常感谢！

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

在此，它 returns 左分支，值，然后是右分支。这可以更简单地完成，如下所示：

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)

来源:: here

Answer 3

@Benedict Randall Shaw 的回答已经很完美了。我只是想以一种 pythonic 的方式为其添加一些乐趣。尽管 doc 不建议使用可变 object 作为默认参数，这将通过将默认可变 list 视为 class 的成员来稍微简化代码 python 函数。

不同之处仅在于 += 被 = 替换了，因为 res 在函数内部始终相同 list object函数 object 已被垃圾回收。

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

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

Inorder Binary Tree Traversal (using Python)

python

list

binary-tree

inorder