Inorderバイナリツリートラバーサル（Pythonを使用）

Question

ツリーのインオーダートラバーサルを実行しようとしています。コード自体は正しく動作していることを除いて、正しく感じます。私はそれがif条件、Pythonでの動作の仕方、あるいはおそらく復帰と何かをしなければならないと感じています。リターンの代わりにプリントを使用すると正しく動作しますが、リターンを使用して正しい答えを得たいと思っています。たとえば、ツリー[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) 

ソース::どのように木がhere