二叉树遍历

Question

二叉树相关知识，使用数据结构中的栈(stack),对二叉树前中后序遍历的实现

Answer 1

老铁你好。不知道你是否已经理解了递归的三种遍历是如何实现的，如果没有，建议先弄明白递归如何实现三种遍历。

说到底，这里的递归起到的实际上是回溯父节点的能力，例如当前递归中，没有了left和right，当前递归就会结束，从而返回到上一层递归中。

这里使用栈，实际上就是想办法用栈代替递归，说到底又是使用栈记录访问节点的路径，以便当前节点找到自己的父节点。如果理解了递归的遍历原理，这里就简单了。

伪代码（前序为例）：

1.访问当前结点a，并将结点a入栈;

2.判断左孩子是否为空：

    空：判断a = 弹栈->右孩子是否为空：

        空：继续弹栈，直到右孩子不为空。跳转到1

    不空：a = a->左孩子。

3.栈为空并且还需要弹栈，结束循环。

Answer 2

这种你百度一下就有的，大一学数据结构书上好像也有吧