题目描述
给定一个二叉树的根节点 ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]讯享网示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围 内
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
java天梯赛基础语法
解题思路
中序遍历的顺序是：
- 先遍历左子树
- 然后访问根节点
- 最后遍历右子树
要实现二叉树的中序遍历，最常见的方式是使用递归。
讯享网
迭代方法使用栈来替代递归。具体步骤如下：
- 从根节点开始，沿着左子树不断往下走，把所有节点压入栈中。
- 当没有左子树时，弹出栈顶节点，访问该节点，然后处理该节点的右子树。
复杂度分析
- 时间复杂度：O(n)，其中 n 是二叉树的节点数，因为每个节点都恰好被遍历一次。
- 空间复杂度：O(h)，其中 h 是二叉树的高度。栈的空间开销取决于树的高度，最坏情况下（退化为链表），空间复杂度为 O(n)。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/7823.html