tree traversal (树的遍历) - 中序遍历 (inorder traversal) - 二叉树的中序遍历

1. tree traversal (树的遍历)

1.1 深度优先搜索 (depth-first search，DFS)

我们采用深度作为优先级，从根节点开始一直到达某个确定的叶子节点，然后再返回根节点到达另一个分支。深度优先搜索策略可以根据根节点、左孩子树和右孩子树的相对顺序被细分为前序遍历、中序遍历和后序遍历。

前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal)

1.2 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS)

我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。

下图中的节点依照不同的策略遍历，访问的顺序均为 1, 2, 3, 4, 5。宽度优先搜索划分层次为 [[1], [2, 3], [4, 5]]。

2. 二叉树的中序遍历

给定一个二叉树，返回它的前序遍历。

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

int* preorderTraversal(struct TreeNode* root, int* returnSize)

输入参数 root 为 NULL 时，如果 return NULL，*returnSize 必须设置为 0。

2.1 迭代实现 - 数组模拟栈 (stack) 的操作

从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压入右孩子再压入左孩子。输出到最终结果的顺序按照 Top -> Bottom 和 Left -> Right，符合前序遍历的顺序。

时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N)，其中 N 是节点的个数，即树的大小。
空间复杂度：取决于树的结构，最坏情况存储整棵树，空间复杂度是 O(N)。

1. 设置一个栈，将根节点 push 到栈中。
2. 循环检测栈是否为空，若不空，则取出栈顶元素，保存其值。
3. 查看栈顶元素右子节点是否存在，若存在则 push 到栈中。查看栈顶元素左子节点，若存在，则 push 到栈中。
4. 继续回到 2. 执行，直到栈空。

3. 中序遍历 (inorder traversal)

中序遍历 (inorder traversal) 顺着左侧通路，自底而上依次访问沿途各节点及其右子树。

迭代式中序遍历 (出栈节点以深色示意)

References

https://leetcode-cn.com/