中序二叉树遍历(使用Python)

Inorder Binary Tree Traversal (using Python)

我正在尝试执行树的中序遍历。代码本身感觉不错,只是它不能正常工作。我感觉它要么与 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 而不加解释,我将不胜感激。非常感谢!

这不起作用的原因是 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 []

改用这个,一个简单的递归::

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

@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

另一种输出列表的方法,优点是您只需向单个列表添加值:

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