4月18日leetcode二叉树几种遍历方式的非递归和递归

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

二叉树的前序中序和后序遍历算法是学习二叉树必不可少的，若是使用c语言遍历前中后序还是比较繁琐的，因为要考虑遍历结果存放的序列大小问题，想要解决这个问题就得想用递归计算二叉树的节点数量，再调用递归子函数完成递归遍历。

解题思路，首先有根结点，用这个根结点进行整个二叉树的节点计算，若为空则返回空，若不为空则返回其结点的左子树和右子树+1；这样整个递归完成后得到所有的结点个数。

然后再主函数中使用得到的大小开出一个数组用来存放每个结点的数据，用一个子函数传参一个数组和根结点的指针，若为空则返回空，若不为空且为中序遍历则调用子函数进入左子树，然后将根结点的数据存入数组，且指针下标加一，再递归进入右子树，因为是递归所以传数组下标的地址，具体代码如下：

然后中序遍历与后序遍历只需要调整递归的子函数与节点数据入数组的顺序即可。代码如下：

递归算法后就是非递归算法：

若使用c语言非递归算法的步骤比递归还要繁琐于是下面用c++来进行非递归：

因为树的无论哪一种遍历方式都是优先深度访问，在到达根结点后需要跳回到他的双亲结点，所以若是不用递归的返回方式就先要解决如何在访问到叶子节点为空时如何回去访问其双亲结点的问题，我们可以利用栈的数据结构来存放其根节点，当一个叶子结点访问完后利用循环访问栈顶的数据，就可以解决且双亲结点的问题。

先序的解题步骤：

1：定义一个栈，再定义一个vector用来存放遍历后的序列，

2；先将根结点赋给一个临时变量cur，利用一层循环迭代cur，若cur不为空。则将粗人中的val尾插入vector中并入栈，因为时先序遍历，可以在访问迭代时顺便就尾插入vector了，直到cur为空循环结束，此时可以将栈顶数据弹出，将栈顶数据赋给cur此时cur为最后根节点的右子树的根节点。

3：若是再给一个外循环将此循环包裹，就又是一个入栈尾插的过程，将外循环的循环写为cur不为空或

栈不为空。若右子树为空，则满足栈不为空的条件，且不进入内循环。直接再次将栈顶数据的右子树给cur，依次迭代直到遍历完所有结点。

代码图：

然后是中序遍历，中序遍历与先序遍历稍有不同，因为在cur迭代时不能先将数据尾插入vector中，过程是先遍历完将数据都入栈，然后cur为空，可以认为左子树为空，然后弹出并得到栈顶数据，此时才可以将数据尾插vector中之后将栈顶数据的左子树赋给cur，进行下一次遍历，之后就与先序遍历一一样了。

代码如下：

 后序遍历又跟前两个遍历又有所不同，因为后序遍历需要在第一次访问当前结点时不尾插vector，而是在左子树访问完成后进入右子树访问完成后再次回到根节点时才可以尾插vector，所以区分是否是第一次访问cur还是第二次访问cur是个问题。可以定义一个二叉树结点p，当第一次访问cue时将cur赋给这个结点，在进行尾插vector时加一个条件判断，若p不等于此结点则证明他已经递归进入过左子树，将左子树并且得到了左子树的结点，此时可以放心地尾插vector了，重要的就是这个条件判断。

 三种遍历的共同点是，都是用cur为空来代替递归结束的判断条件，并用栈来保存上一次迭代的双亲结点以便下一次迭代使用。

tips:每次内循环为空且弹出栈顶元素并得到他时表示左子树已经访问完成，且当前位置位于第一个根节点，此时又两个选择第一个选择是将此节点尾插入vector，此选择仅适用于中序遍历，然后将右子树给cur进行下一次循环，而第二个选择时不尾插vector，先进入右子树遍历，待右子树遍历完成后在进行尾插vector此选择适用于后序遍历，不存在先序遍历的选择因为先序遍历已经在迭代时尾插了。