理解树遍历的递归 [英] Understanding Recursion on Tree Traversals

问题描述

我试图了解递归的工作原理以及遍历二叉树的工作原理.

I am trying to understand how recursion works and how traversing a Binary Tree works.

好吧，据我所知，递归正在调用它自己内部的一个函数.有点像循环.

Okay so from what I know, recursion is calling a function within it self. Kind of like looping.

现在我得到了如何在二叉树上进行postOrder遍历的代码.

Now I was given the code on how to do a postOrder traversal on a Binary Tree.

(注意这不是我的代码，我只是想通过这段代码了解递归是如何工作的)

(Note this is not my code, I am just trying to understand how recursion works through this code)

 # 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 遍历是右-左-中，所以先子后父.

Now from what I understand a PostOrder traversal goes right-left-middle so child first then parent.

这是我认为发生递归的 2 行.

Here are the 2 lines where I think recursion is taking place.

    self.postorderTraversalRec(root.left, solution)
    self.postorderTraversalRec(root.right, solution)

据我所知，第一行告诉程序递归遍历所有左节点，直到到达末尾.然后它告诉程序遍历所有左边的节点，直到它到达终点.

From what I can understand is that the first line tells the program to recursively go through all the left nodes till it reaches the end. Then it tell the program to go through all the left hand nodes till it reaches the end.

但我面临的问题是，我无法理解这是如何进行 PostOrder 遍历的.对我来说，它看起来像一个 PreOrder 遍历.

But the problem I am facing is that, I cannot understand how this does a PostOrder traversal. To me it looks like a PreOrder traversal.

推荐答案

后序遍历如下:

1. 遍历左子树.
2. 遍历右子树.
3. 访问根.

这正是这里发生的事情.对于任何给定的节点(root)，首先访问左子树(root.left)，然后访问右子树(root.right)，然后是节点本身 (root.val).

Which is exactly what is happening here. For any given node (root), first you visit the left sub-tree (root.left), then the right sub-tree (root.right), then node itself (root.val).

遍历类型的前"或后"部分是指当前节点的值被访问时，无论是在访问子节点之前(pre-)，之后(post-)，还是访问之间每个子节点(按顺序遍历).在您的示例代码中，在遍历子节点后访问当前节点的值.所以，这是后序遍历.

The "pre" or "post" part of the traversal-type refers to when the value of the current node is visited, either before visiting the child nodes (pre-), after (post-), or even between visiting each child node (in-order traversal). In your example code the current node's value is visited after traversing the children. So, it's post-order traversal.

这篇关于理解树遍历的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！