面试理想汽车，跪了。。

大家好，我是吴师兄。

前几天看到一个有意思的帖子：理想汽车面试，聊到了二叉树的后序遍历，求职者说后序遍历是 左右中 ，面试官坚持说不是，把求职者整懵逼了。

答案或许是因为和面试官面对面的缘故。。。

玩归玩闹归闹，今天我们来系统复习一下如何通过掌握一套代码，使用一个非递归的方式来同时处理前序、中序和后序遍历。

尽管最终只返回了前序遍历的结果，代码的结构为处理三种遍历提供了基础 。

这种方法利用了栈（Stack）来 追踪访问过的节点和它们的状态 ，允许在不使用递归的情况下遍历树。下面是对代码中关键部分的详细解释：

核心变量

• preorderResult ：用于存储前序遍历的结果。
• inorderResult 和 postorderResult ：虽然这两个列表被初始化，但它们并未被用于存储中序和后序遍历的结果（相关代码被注释掉了）。
• stack ：用于存储遍历过程中的节点，特别是当需要回溯到父节点时。
• node ：当前正在访问的节点。
• nodeState ：表示节点遍历的当前状态，它有三个可能的值： nodeLeft （100）、 nodeRight （200）、 nodeUp （300），分别表示节点的左孩子、右孩子已经被处理，或者都已处理完毕，准备回溯到父节点。

遍历逻辑

1. 前序遍历（Pre-order） ：在节点状态为 nodeLeft 时，即在处理任何孩子之前，节点的值被添加到 preorderResult 。
2. 中序遍历（In-order） ：在此代码示例中，虽然有相应的列表初始化，但实际添加到中序遍历结果的操作被注释掉了。理论上，在节点状态从 nodeLeft 变为 nodeRight ，即处理完左孩子后，应添加到 inorderResult 。
3. 后序遍历（Post-order） ：同样，后序遍历的结果添加操作也被注释掉了。在所有孩子都被处理完毕，节点状态为 nodeUp 时，应添加到 postorderResult 。

状态转换

• 当节点有左孩子时，进入左子树，状态保持 nodeLeft 。
• 当左子树被完全访问（或不存在左子树），节点状态变为 nodeRight ，尝试访问右子树。
• 当右子树被完全访问，节点状态变为 nodeUp ，表示准备回溯到父节点。
• 使用栈来回溯到父节点，并根据父节点和当前节点的关系更新状态。

结束条件

循环继续直到所有节点都被访问，即当 node 为 null 且无法从栈中获取更多节点时。

这个方法展示了如何在没有递归的情况下同时处理三种基本的二叉树遍历。通过调整和启用中序和后序遍历的相关代码，可以轻松修改该代码来收集这三种遍历的结果。这种方法的优点是只需要遍历一次树，且不需要递归调用，从而减少了调用栈的使用，对于深度很大的树来说，这是一个显著的优势。

代码如下，建议自己模拟一下整个过程，30 分钟完全可以彻底掌握。

class Solution {
    public List preorderTraversal(TreeNode root) {

        // 设置一个数组用来保存二叉树前序遍历的结果
        List preorderReslut = new ArrayList<>();

        // 设置一个数组用来保存二叉树中序遍历的结果
        List inorderResult = new ArrayList<>();

        // 设置一个数组用来保存二叉树后序遍历的结果
        List postorderResult = new ArrayList<>();

        // 设置一个栈，用来保存路径
        Stack stack = new Stack<>();

        // 设置一个节点，一开始指向根节点
        TreeNode node = root;

        // 设置三种状态，方便表示当前遍历当前节点的时候进行到哪一步了
        // 每个节点都有 左、右、上 这三种状态
        // 按照 左 --> 右 --> 上 的顺序观察每个节点

        // 左代表该节点的左右孩子节点都没有遍历
        int nodeLeft = 100;

        // 右代表该节点的左孩子节点已经遍历，右孩子节点还没有遍历
        int nodeRight = 200;

        // 上代表左右孩子节点都已经遍历，需要返回到它的父节点
        int nodeUp = 300;

        // 每个节点的初始化状态都是从 左 开始
        int nodeState = nodeLeft;


        // 对二叉树进行遍历
        while(node != null){

            // 位置 ① 

            // 如果当前节点的状态是【左】，说明该节点的左右孩子节点都没有遍历
            if(nodeState == nodeLeft){
                // 把当前节点加入到二叉树前序遍历的结果数组中
                preorderReslut.add(node.val);

                // 如果当前节点有左子树
                if(node.left != null){

                    // 先把当前节点加入到栈中，用来记录节点移动的路径
                    stack.push(node);

                    // 开始观察当前节点的左孩子节点，代码来到了位置 ① 
                    node = node.left;
                }else{

                    // 如果当前节点没有左子树，切换当前节点的状态为【右】
                    // 代码来到了位置 ① 
                    nodeState = nodeRight;
                }

            }else if(nodeState == nodeRight){ // 如果当前节点的状态是【右】，说明该节点的左孩子节点已经遍历，右孩子节点还没有遍历

                // 把当前节点加入到二叉树中序遍历的结果数组中
                // inorderResult.add(node.val);

                // 如果当前节点有右子树
                if(node.right != null){

                    // 先把当前节点加入到栈中，用来记录节点移动的路径