之前也知道递归的实质就是Stack，但一直也没怎么思考。今天看到一个二叉树中序遍历的算法题，想着可以自己用栈实现一下。

  首先中序遍历二叉树的访问顺序是左子树-根节点-右子树。既然是树的遍历，我们需要定义结点的数据结构。结点的数据结构用java实现如下：

class TreeNode{
    int val;         // 结点的数据
    TreeNode left;   // 左子节点
    TreeNode right;  // 右子节点
  
    public TreeNode() {
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

}

  接着来实现用Stack访问树结点的部分。对于Stack我们知道是先进后出的方式进行数据的访问，既然我们想中序遍历二叉树（左子树-根节点-右子树），那么数据的进Stack方式是（根节点-左子树）。整个过程是 根节点有左子树就把左子树压进Stack，在更新根节点为当前的左节点，再进行上述判断直到左子树不存在为止。之后把Stack空间中最上面的弹出Stack，再判断当前结点是否存在右子树，有的话就压进Stack，之后循环执行上述过程。代码实现如下：

    public static List<Integer> inorderTraveral(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();

        while (root != null || !stack.isEmpty()){

            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
         return list;
    }

测试代码如下：

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        TreeNode treeNode3 = new TreeNode(3,null,null);
        TreeNode treeNode2 = new TreeNode(2,treeNode3,null);
        TreeNode root = new TreeNode(1,null,treeNode2);
        list = inorderTraveral(root);
        System.out.println(list);
    }

通过这个例子我对递归的实现有了更深的理解，能用递归实现的一定可以用循环来实现。整个函数调用过程中最重要的就是Stack的应用。