我也知道递归的本质是Stack，但我一直没怎么想。 今天，看到二叉树中顺序扫描的算法问题，我觉得自己可以在堆栈上实现。
首先，按照中顺序遍历二叉树的访问顺序是左子树―根节点―右子树。 既然是树的遍历，就有必要定义节点的数据结构。 节点的数据结构在java中实现如下。
类treenode { int val； //节点的数据TreeNode left； //左子节点TreeNode right； //右子节点publictreenode(}publictreenode ) intval、TreeNode left、TreeNode right ) { this.val=val； this.left=left； this.right=right； 接着，通过Stack实现访问树节点的部分。 对于堆栈，已知以先进先出方式进行数据的访问，但既然想按照中顺序遍历二叉树[左子树-根节点-右子树]，则数据的进入堆栈方式为[根节点-左子树]。 如果根节点有左子树，则将左子树推入堆栈，将根节点更新为当前的左节点，进行上述判断，直到左子树不存在为止。 然后，取出堆栈空间顶部的弹出堆栈，判断当前节点是否有右子树，如果有，推入堆栈，然后循环运行上述过程。 代码实现如下：
publicstaticlistintegerinordertraveral (趋势根) { ListInteger list=new ArrayList )； dequetreenodestack=newlinkedlisttreenode (； wile (路线！=空| |！ stack.isEmpty () ) while ) (root！=null}{stack.push(root )； 根=根.左； } root=stack.pop (； list.add (根. val )； root=root.right； }返回列表； }测试代码如下。
publicstaticvoidmain (字符串[ ] args ) { ListInteger list=new ArrayList； treenode treenode3=新趋势(3，null，null )； treenode treenode2=新趋势(2，treeNode3，null )； treenoderoot=newtreenode(1，null，treeNode2)； list=inordertraveral (根)； system.out.println (列表； }通过这个例子，我对递归的实现有了更深的理解。 递归能实现的东西一定能在循环中实现。 函数调用过程中最重要的是Stack的应用。