中序遍历二叉树 Posted on 2021-06-09 00:00:00 2021-06-26 00:00:00 by Author 摘要 中序遍历二叉树，除了用递归的方式，你还会其他的方式吗 # 中序遍历二叉树 1. 题目描述 - 中序遍历二叉树，一般用的是递归方法实现的，你可以使用非递归方式实现吗？(提示：使用栈） 2. 示例描述 - 示例一 - 输入：  - 输出：[1,3,2] - 示例二 - 输入：  - 输出：[1, 7, 3, 8, 2, 9, 6] 3. 解题思路 - 同样对于二叉树的中序遍历，我们用递归的写法其实主要代码只要4到5行就能完成。但是如果不让使用递归的方式，那需要怎么取解决尼，前面一篇文章我们谈到了前序遍历二叉树，不用递归的方式实现，大家如果明白那篇文章使用迭代的方式，那么中序遍历二叉树的迭代方法和前序遍历二叉树的方式差不多，只需要改变节点进栈的方式与出栈时候的方式。 - 对于中序遍历二叉树，我们都晓得，先遍历节点的左孩子，然后在遍历该节点，然后在遍历该节点下的右孩子。直到整棵二叉树都遍历完成，那么这棵树的中序遍历也就完成。所以用迭代的方式就是，如果节点有左孩子，那么就把该节点压入栈中，继续寻找左孩子节点的左孩子，直到左孩子下的左孩子节点为空位置，然后此时也就到了初始节点左孩子的叶子节点，然后访问该节点，之后该节点出栈，并且把该出栈的节点右孩子压入栈中，然后在找压入栈中的右孩子节点的左孩子的节点，直到找到叶子节点位置。然后重复以上的步骤，栈中为空为止，也就遍历这个二叉树了。其实讲了这么多，我感觉我自己讲的也是模棱两可，具体实践还是需要自己动手画一下，接下来就看看一张动态的图来理解吧(这个图是来源于代码随想录公众号) [](http://e-blog.oss-cn-shanghai.aliyuncs.com/resources/user/getopsite/article/2021-06-09/20210608235439.gif) 4. 代码实现 ```java public List<Integer> inorderTraversal(TreeNode root) { //定义返回结果集 List<Integer> result = new ArrayList<>(); //定义一个栈，栈中元素类型为节点类型 Stack<TreeNode> stack = new Stack<>(); //首先判断给出的根节点是否为空 if (root == null) { //如果为空，直接返回 return result; } //迭代法开始 //如果遍历的节点不为空，说明该节点存在，接下来看加入其左孩子,说明已经到达左孩子的叶节点 //那么在看栈为空吗，如果为空，说明该二叉树已经遍历完成 //如果不为空，说明该节点下所以左孩子的中序遍历完成，那么该节点可以出栈，然后把出栈的节点的右孩子压入栈中 //继续执行中序遍历的操作， while (root != null || !stack.isEmpty()) { //如果遍历的节点不为空，那么把该节点压入栈中，继续寻找该节点的左孩子 if (root != null) { stack.add(root); root = root.left; } //如果该节点为空，说明该节点的父节点没有左孩子了，那么访问该空节点的父节点，然后把该父节点移除栈中，加入右孩子节点 //继续寻找加入右孩子节点的左孩子，这样就能形成迭代的关系 else { //弹出栈中的节点 root = stack.pop(); //加入结果集合中 result.add(root.val); //加入该节点的右孩子,继续中序遍历 root = root.right; } } //返回结果 return result; } ```
{{ item.content }}
{{ child.content }}