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