94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
方法一：递归实现（最简单）
# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def inorderTraversal(self, root: TreeNode) -> list[int]:result = []def dfs(node):if not node:returndfs(node.left)result.append(node.val)dfs(node.right)dfs(root)return result
方法二：迭代实现（使用栈）
class Solution:def inorderTraversal(self, root: TreeNode) -> list[int]:result = []stack = []current = rootwhile current or stack:while current:stack.append(current)current = current.left # 一直往左走current = stack.pop()result.append(current.val)current = current.right # 然后往右走return result
