有序二叉树遍历(使用Python) [英] Inorder Binary Tree Traversal (using Python)

问题描述

我正在尝试对树进行有序遍历.该代码本身感觉不错，除非它无法正常工作.我觉得它与if条件，append如何在python中工作或可能与return有关.我认为，如果我使用print而不是return，则此方法可以正常工作，但是我希望能够使用return并仍然获得正确的答案.例如，对于树[1，None，2,3]，我的代码返回[1]，这显然是错误的.

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.

此外，是否可以使用列表理解来解决此问题?如果是这样，将非常感谢任何示例代码.

Additionally is it possible to solve this problem using list comprehension? If so, any sample code would be greatly appreciated.

这是我的代码:

    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上已经按顺序遍历了很多次(但是很多次)，但是它们都没有帮助我理解为什么我的理解是错误的.如果有人帮助我学习如何纠正我的方法，而不是简单地发布另一个没有说明的链接，我将非常感激.非常感谢！

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!

推荐答案

之所以不起作用，是因为res只附加了您赋予它的第一个节点的值.每次您递归地调用该函数时，它只会产生一个新的分辨率.不过，这是一个简单的解决方法，如下所示:

The reason this doesn't work is that res only 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:

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

这篇关于有序二叉树遍历(使用Python)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！