题目：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

题目

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

示例:

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法

1. 递归

常规解法，直接上代码，由于这边设置的函数返回要求是向量类型的，因此，我们可以设置一个全局的向量，方便在递归的过程中，进行数据的Push

2. 非递归

非递归算法，容易联想到stack的方法。这边需要注意怎样避免重复的push已读数据。

通过前探的思想（即判断先进入子节点，然后判断子节点是否存在）可以有效避免重复的push

如果不这么做，而采用后探（先判断子节点是否存在，然后再选择是否进入），这样做如果不设置标记为，常常会重复的push

例如层序遍历表示的只有左孩子的树（1,2,null），如果用后探，则先在根节点1判断有没有左孩子节点，这个时候会得到2，然后栈中push节点2，再判断节点2不存在左孩子，根据中序遍历，输出2的值，这个时候栈中pop出节点2，又回到了节点1，这个时候就需要判断左孩子节点是否已经访问过。否则又会再一次进入节点2

采用前探的思想，对于只有左孩子的树（1,2,null），会先把节点1，节点2入栈，然后再进入到2的左孩子中，由于2的左孩子为NULL，因此可以直接输出2的值，然后弹出2，同时指向2的右孩子。由于2的右孩子也不存在，因此再选择从栈中弹出一个，以此类推