LeetCode94. 二叉树的中序遍历

**二叉树的中序遍历**

中序遍历是二叉树的一种遍历方式，按照从左子树到根节点再到右子树的顺序进行遍历。这种遍历方式可以帮助我们更好地理解二叉树的结构和特点。

**中序遍历的定义**

中序遍历的定义是：对于一棵二叉树 T，如果它的左子树为空，则输出 T 的值；否则，先输出 T 的左子树的值，然后输出 T 的值，最后输出 T 的右子树的值。

**中序遍历的实现**

我们可以使用递归或迭代两种方式来实现中序遍历。下面是递归和迭代两种方式的代码示例：

### 递归方式

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef inorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 res = []
 if not root:
 return res # 递归左子树 left_res = inorderTraversal(root.left)
 # 输出根节点的值 res.append(root.val)
 # 递归右子树 right_res = inorderTraversal(root.right)
 # 合并结果 return left_res + res + right_res# 示例代码root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(inorderTraversal(root)) # [4,2,5,1,3]

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef inorderTraversal(root):
 """
 :type root: TreeNode :rtype: List[int]
 """
 res = []
 stack = []
 while True:
 # 迭代左子树 while root:
 stack.append(root)
 root = root.left # 如果栈空，则结束遍历 if not stack:
 break # 输出栈顶元素的值 node = stack.pop()
 res.append(node.val)
 # 迭代右子树 root = node.right return res# 示例代码root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(inorderTraversal(root)) # [4,2,5,1,3]