本文详细探讨了五种二叉树中序遍历算法，包括递归、迭代、莫里斯遍历、线索二叉树和栈的迭代，评估了它们的效率和实用性。 题目描述 给定一个二叉树的根节点 root，返回它的中序遍历。 输入格式 root：二叉树的根节点。 输出格式 返回中序遍历结果的列表。 示例 示例 1 输入: root = [1,null,2,3]输出: [1,3,2] 方法一：递归 解题步骤

目录   题目： 解题思路： 方法一：递归(时间O(N),空间O(N)) 方法二：栈(时间O(N),空间O(N)) 方法三：莫里斯遍历(时间O(N),空间O(1)) 解题思路： 方法一：递归 方法二：栈 方法三：莫里斯 题目： 题目链接： https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

144. 二叉树的前序遍历 我们写二叉树的遍历时，一般有两种方式，迭代和递归。然而还有一种神奇的算法，也可以作我们的二叉树递归，且空间复杂度为O(1)，要知道，我们迭代和递归都是需要额外栈空间的 递归和迭代网上都有很多的资料，虽然莫里斯算法资料是有，但是很少有图解，我们理解起来就会非常困难。下面这篇文章我们主要针对的就是我们的Mrror算法(莫里斯算法) Morris 遍历的核心思想

什么是Morris遍历 其实就是把空间复杂度优化到O(1)的二叉树遍历算法。 对于一般的遍历算法，我们都是利用栈来存储之后需要再次访问的节点。最差情况下，我们需要存储整个二叉树节点。所以空间复杂度为O(n)。而Morris遍历则是将空间复杂度降到了O(1)级别。Morris遍历用到了“线索二叉树”的概念，其实就是利用了叶子节点的左右空指针来存储某种遍历前驱节点或者后继节点。因此没有使用额