Я пытаюсь понять, как работает рекурсия и как работает обход двоичного дерева.
Итак, насколько я знаю, рекурсия вызывает функцию внутри себя. Что-то вроде зацикливания.
Теперь мне дали код, как выполнить обход postOrder в двоичном дереве.
(Обратите внимание, что это не мой код, я просто пытаюсь понять, как работает рекурсия в этом коде)
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of integers
def postorderTraversal(self, root):
solution = []
self.postorderTraversalRec(root, solution)
return solution
def postorderTraversalRec(self, root, solution):
if root == None:
return
self.postorderTraversalRec(root.left, solution)
self.postorderTraversalRec(root.right, solution)
solution.append(root.val)
Теперь, насколько я понимаю, обход PostOrder идет справа-налево-посередине, поэтому сначала дочерний, а затем родительский.
Вот 2 строки, где, как мне кажется, происходит рекурсия.
self.postorderTraversalRec(root.left, solution)
self.postorderTraversalRec(root.right, solution)
Насколько я понимаю, первая строка говорит программе рекурсивно пройти через все левые узлы, пока не достигнет конца. Затем он говорит программе пройти через все левые узлы, пока не достигнет конца.
Но проблема, с которой я столкнулся, заключается в том, что я не могу понять, как это делает обход PostOrder. Для меня это выглядит как обход PreOrder.
