In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once.
We do traverse a tree by depth-first search or breadth-first search. For depth-first search (DFS), there are three methods/patterns: pre-order, in-order and post-order.
Pre-order, NLR
- Access the data part of the current node (in the figure: position red).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.
In-order, LNR
- Traverse the left subtree by recursively calling the in-order function.
- Access the data part of the current node (in the figure: position green).
- Traverse the right subtree by recursively calling the in-order function.
Post-order, LRN
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Access the data part of the current node (in the figure: position blue).
Depth-first traversal (dotted path) of a binary tree:
- Pre-order (node access at position red ●): F, B, A, D, C, E, G, I, H;
- In-order (node access at position green ●): A, B, C, D, E, F, G, H, I;
- Post-order (node access at position blue ●): A, C, E, D, B, H, I, G, F.
Given a tree root, write functions to do pre-order, in-order and post-order traversal and output the node data respectively.
Sample Input:
root = [1, 2, 3, 4, 5, 6, 7]
Sample Output:
Pre-order: 1 2 4 5 3 6 7
In-order: 4 2 5 1 6 3 7
Post-order: 4 5 2 6 7 3 1
数据结构和算法：初级练习题 #39 – 遍历二叉树
在计算机科学里，树的遍历（也称为树的搜索）是图的遍历的一种，指的是按照某种规则，不重复地访问某种树的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。
与那些基本上都有标准遍历方式（通常是按线性顺序）的线性数据结构（如链表、一维数组）所不同的是，树结构有多种不同的遍历方式。从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点）、遍历左边子节点、遍历右边子节点。这三个步骤的先后顺序也是不同遍历方式的根本区别。
由于从给定的某个节点出发，有多个可以前往的下一个节点（树不是线性数据结构），所以在顺序计算（即非并行计算）的情况下，只能推迟对某些节点的访问——即以某种方式保存起来以便稍后再访问。常见的做法是采用栈（LIFO）或队列（FIFO）。由于树本身是一种自我引用（即递归定义）的数据结构，因此很自然也可以用递归方式，或者更准确地说，用corecursion，来实现延迟节点的保存。这时（采用递归的情况）这些节点被保存在call stack中。
遍历方式的命名，源于其访问节点的顺序。最简单的划分：是深度优先（先访问子节点，再访问父节点，最后是第二个子节点）？还是广度优先（先访问第一个子节点，再访问第二个子节点，最后访问父节点）？ 深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）、根节点放在左节点和右节点的中间，称为中序（in-order）、根节点放在右节点的右边，称为后序（post-order）。对广度优先而言，遍历没有前序中序后序之分：给定一组已排序的子节点，其“广度优先”的遍历只有一种唯一的结果。
上面的图例展示了深度优先的三种遍历方式：前序（红色）、中序（绿色）、后序（蓝色）。
给定一颗二叉树，用深度优先的三种遍历方式访问每一个结点并输出其数值。
输入样例：
root = [1, 2, 3, 4, 5, 6, 7]
输出样例：
Pre-order: 1 2 4 5 3 6 7
In-order: 4 2 5 1 6 3 7
Post-order: 4 5 2 6 7 3 1
Python Solution
