Inorder二叉树遍历(使用Python)

Question

我正在尝试执行树的顺序遍历.代码本身感觉正确,除非它不能正常工作.我有一种感觉,它必须与if条件,如何附加在python中工作,或者可能与返回.如果我使用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上已经有人询问遍历(很多次),但是没有一个能帮助我理解为什么我的理解是错误的.如果有人帮助我学习如何纠正我的方法而不是简单地发布另一个没有解释的链接,我将非常感激.非常感谢!

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)

来源：：这里