class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def inorderTraversal(self, root):
        result=[]
        stack=[]
        current = root

        while current or stack:

            while current:
                stack.append(current)
                current=current.left


            current=stack.pop()
            result.append(current.val)

            current=current.right

        return result

1. 定义树节点类（TreeNode）

python

运行

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

  • 功能：这个类用来表示二叉树的一个节点。
  • 解释：__init__(self, x)：这是类的构造函数，当你创建一个新节点时会自动调用。self.val = x：节点的值（比如数字 1、2、3）。self.left 和 self.right：分别指向左子节点和右子节点，初始为 None（空）。

举例：创建节点 1，左子节点是 2，右子节点是 3：

python

运行

node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node1.left = node2  # 节点1的左子节点是节点2
node1.right = node3 # 节点1的右子节点是节点3

2. 定义解决方案类（Solution）

python

运行

class Solution:
    def inorderTraversal(self, root):
        result = []  # 存储遍历结果的列表
        stack = []   # 辅助栈，用于暂存节点
        current = root  # 当前指向的节点，初始为根节点

  • 功能：这个类包含中序遍历二叉树的方法。
  • 解释：inorderTraversal(self, root)：方法接收二叉树的根节点 root 作为参数。result = []：创建一个空列表，用于存放遍历结果（比如 [1, 2, 3]）。stack = []：创建一个空栈（用列表模拟），帮助我们记住需要处理的节点。current = root：从根节点开始遍历。

3. 主循环：遍历左子树并处理节点

python

运行

        while current or stack:  # 当当前节点不为空 或 栈不为空时
            # 遍历到最左节点
            while current:
                stack.append(current)  # 将当前节点压入栈
                current = current.left  # 移动到左子节点

  • 功能：找到当前子树的最左节点，并将路径上的所有节点压入栈。
  • 解释：while current or stack：只要当前节点不为空 或者 栈里还有节点，就继续循环。内层 while current：一直向左走，把经过的每个节点都压入栈（因为中序遍历需要先处理左子树）。stack.append(current)：把当前节点压入栈。current = current.left：移动到左子节点。如果左子节点为空，内层循环结束。

举例：对于树 1(2, 3)，这个循环会先把 1 → 2 依次压入栈，直到 current 变为 None（因为节点 2 的左子节点是空）。

4. 处理当前节点并转向右子树

python

运行

            # 访问当前节点
            current = stack.pop()  # 从栈中弹出节点
            result.append(current.val)  # 将节点的值加入结果列表
            
            # 转向右子树
            current = current.right  # 移动到右子节点

  • 功能：处理当前节点（访问值），然后转向右子树继续遍历。
  • 解释：current = stack.pop()：从栈中弹出最顶部的节点（比如前面例子中的节点 2）。result.append(current.val)：把弹出节点的值加入结果列表（比如 [2]）。current = current.right：移动到弹出节点的右子节点（比如节点 2 的右子节点）。如果右子节点为空，下次循环会继续从栈中弹出节点。

举例：

  • 弹出节点 2，加入结果列表 [2]，然后尝试访问节点 2 的右子节点（如果有）。
  • 如果右子节点为空，下次循环会弹出节点 1，加入结果列表 [2, 1]，再访问节点 1 的右子节点（即节点 3）。