场景化二叉树遍历

前言

对于一道抽象的题目，将它放入实际的场景可以说是一个非常好的帮助理解的方式，对于二叉树的遍历方式，有前序遍历，中序遍历，后序遍历；用递归的方式求解这很容易，但是如果使用迭代的方式就有点抽象了，所以下面以中序遍历为例，讲讲如何设计它的迭代求解；

场景再现

现在有个迷宫，这个迷宫的结构其实就是一个二叉树，入口从根节点开始，迷宫的鸟瞰图如下：

现在由我们自主设计的机器人，它每次选择二叉路口是都会优先选择左边（中序遍历优先遍历左子树–>节点–>右子树），碰壁后就会回到上一个路口，然后往右走，如果右边依然碰壁，说明这个路口是死路，所以回到上上个路口，当然每当第二次回到路口我们一定往右，并且机器人需要加一次由（输出节点的值）；好了，场景已经设计成功，下面就是将思路转变为代码

代码

1.首先是大框架：先一直走左，然后碰壁回到上一个路口才往右；显然我们的记录自己走过的路才知道怎么回去，于是机器人会在地图上记录下自己每次走过的路口，当遇到墙壁，我们就回到最近经过的路口，也就是上一个路口，并且加油，显然数据结构应该使用栈；

public List<Integer> solution(TreeNode root){
    // 1.我们的地图
    Stack<TreeNode> stack = new Stack();

    // 2.遍历的顺序
    List<Integer> valList = new ArrayList<>();
    
    // 3.路口是通的，优先往左
    if(root != null){
        // 4.记录经过的路口，方便下次回来
        stack.push(root);

        // 5.往左寻找下一个路口
        root = root.left;
    }else{
        // 6.此路不通，回到地图上记录的最近经过的路口
        root = stack.pop();

        // 7.加一次油
        valList.add(root.val);

        // 8.往右寻找路口
        root = root.right;
    }

}

2.此时我们还不能到达重点，我们要一直重复先走左再走右的行为，才能最终到达终点，所以应该来个循环，不过条件是怎么样的呢？试想每次碰壁回头，说明该路口走不到终点，所以机器人在这个路口画了一个叉叉（出栈）；当机器人到达重点所以路口应该都已经画了叉叉（栈为空）；而终点后面没有路了（root == null）,这两个条件满足机器人就判断它真的到终点了；

public List<Integer> solution(TreeNode root){
    // 1.我们的地图
    Stack<TreeNode> stack = new Stack();

    // 2.遍历的顺序
    List<Integer> valList = new ArrayList<>();
    
    while(root != null || !stack.empty()){
            // 3.路口是通的，优先往左
            if(root != null){
                // 4.记录经过的路口，方便下次回来
                stack.push(root);

                // 5.往左寻找下一个路口
                root = root.left;
            }else{
                // 6.此路不通，回到地图上记录的最近经过的路口
                root = stack.pop();

                // 7.加一次油
                valList.add(root.val);

                // 8.往右寻找路口
                root = root.right;
            }
    }

    return valList;

}