Inorder Binary Tree Traversal (используя Python)

Question

Я пытаюсь выполнить обход дерева по порядку. Сам код чувствует себя хорошо, за исключением того, что он не работает должным образом. У меня есть чувство, что он должен либо работать с условием if, как append работает на python, либо что-то, возможно, с возвратом. Это работает правильно, если я использую печать вместо возврата, я думаю, но я хочу иметь возможность использовать 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) 

Источник :: here