难度: Easy
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Submission
运行时间: 36 ms
内存: 14.8 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
stack = []
result = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
result.append(cur.val)
cur = cur.right
return result
Explain
这个题解使用了迭代的方式来实现二叉树的中序遍历。具体思路是：用一个栈来保存节点，先将根节点压入栈中，然后进入循环。在每次循环中，如果当前节点不为空，就将其压入栈中，并将当前节点更新为其左子节点，直到当前节点为空。当前节点为空时，说明已经到达了最左边的叶子节点，此时从栈中弹出一个节点，将其值加入结果列表中，并将当前节点更新为其右子节点。重复这个过程，直到当前节点和栈都为空，遍历结束。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
stack = []
result = []
cur = root
while cur or stack:
# 将当前节点及其所有左子节点压入栈中
if cur:
stack.append(cur)
cur = cur.left
# 当前节点为空，说明已经到达最左边的叶子节点
else:
# 从栈中弹出一个节点，加入结果列表
cur = stack.pop()
result.append(cur.val)
# 将当前节点更新为其右子节点
cur = cur.right
return result
Explore
在二叉树的中序遍历中，遵循的顺序是左-根-右。因此，首先需要访问到最左边的节点，确保按照正确的顺序处理每个节点。通过不断将左子节点压入栈中，我们能够先到达并处理树的最左侧，即最深层的左子节点，然后再依次向上回溯到父节点和右子节点。这种方式确保了每个节点都是在其所有左子节点被处理之后才被访问。
栈在这种迭代方法中扮演了一个关键角色，主要用于保存暂时无法处理的节点（因为它们的左子节点还未完全访问）。栈帮助维持访问顺序，确保在处理完所有左子节点后能够回到当前节点，然后转到右子节点。这种后进先出（LIFO）的特性正是中序遍历所需的，因为它确保了节点访问的顺序符合左-根-右的要求。
这种迭代方法处理的是节点的物理位置而非节点的值，因此即使存在值相同的节点，遍历过程中每个节点都会被访问一次，并按照中序遍历的顺序返回其值。算法依赖于树的结构，而不是节点值的唯一性，所以不会有遗漏或重复的问题，每个节点都会被精确地访问并记录一次。
在迭代过程中，节点首先被推入栈中，然后在到达最左侧节点后开始逐一弹出并访问。每个节点在被访问（即加入结果列表）之后，会将其右子节点设置为当前节点以继续遍历过程。这一过程确保了每个节点在整个遍历中仅被访问一次，因为一旦节点被弹出栈并处理，就不会再次被压入栈。