[数据结构与算法]2021-09-13

关于二叉树递归与非递归遍历的出入栈情况

重温数据结构，发现第一次学的时候并没有对二叉树非递归与递归遍历时的栈进行区分，这两种情况是不一样的

以上图的二叉树的前序遍历为例，如果是递归遍历，则栈的变化如下左

如果是非递归遍历（最普遍的前序遍历非递归算法），则栈的变化如上图右

还有一点要特别说明，递归进栈的是方法，而方法想要出栈必须全部执行完，因此递归遍历的栈中当某次调用方法传入的实参是非叶节点那么该次方法一定在它的子节点的那次方法后面出栈
而非递归进栈的是结点就没有那么多问题了

如果本文有什么问题欢迎在评论区指出，谢谢！