94. 二叉树的中序遍历(Swift实现, 迭代)

题目描述

在这里插入图片描述

使用迭代方法解题

class TreeNode {var val: Intvar left: TreeNode?var right: TreeNode?init(_ val: Int) {self.val = valself.left = nilself.right = nil}
}func inorderTraversal(_ root: TreeNode?) -> [Int] {var result = [Int]()    // 用于存储中序遍历的结果var stack = [TreeNode]() // 用于模拟递归的栈var current = root       // 从根节点开始// 当当前节点不为空或栈不为空时继续循环while current != nil || !stack.isEmpty {// 不断将当前节点的左子节点压入栈中，直到当前节点为空while let node = current {stack.append(node)current = node.left}// 弹出栈顶节点，并将其值添加到结果数组current = stack.removeLast()result.append(current.val)// 将当前节点指向弹出节点的右子节点current = current.right}return result
}// 示例用法：
// 构建一个示例二叉树
//      1
//     / \
//    2   3
//   / \
//  4   5let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)// 调用中序遍历函数
let result = inorderTraversal(root)
print(result)  // 输出: [4, 2, 5, 1, 3]

分析

理解迭代方式的二叉树中序遍历确实需要一些时间，因为它涉及到手动管理一个栈来模拟递归过程。

手动管理一个栈来模拟递归过程，主要在于理解递归调用的本质：保存当前的执行状态，然后在处理完子任务后恢复这个状态。以下是一些窍门和技巧，帮助你更好地理解和实现这种方式：

理解递归和迭代的等效性

递归调用栈：
- 每次递归调用，系统会把当前函数的状态（变量、执行位置等）压入系统栈。
- 当子任务完成后，系统会从栈中恢复上一次的状态继续执行。
迭代模拟递归：
- 我们需要手动管理一个栈，把当前节点和相关信息压入栈中。
- 在处理子任务时，可以从栈中恢复之前的状态。

栈操作的核心逻辑

中序遍历的递归方式：

func inorderTraversal(_ root: TreeNode?) -> [Int] {guard let root = root else { return [] }return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
}

转换为迭代方式：

步骤详细解析

初始化：
- 使用一个栈来存储节点。
- 使用一个变量 current 来追踪当前节点。
模拟递归的左子树处理：
- 不断将当前节点压入栈，并移向左子节点，直到当前节点为空。
- 这一步类似递归调用到最左子节点的过程。
处理节点并移向右子树：
- 弹出栈顶节点，处理该节点（例如添加到结果数组中）。
- 将 current 指向该节点的右子节点。

具体代码

class TreeNode {var val: Intvar left: TreeNode?var right: TreeNode?init(_ val: Int) {self.val = valself.left = nilself.right = nil}
}func inorderTraversal(_ root: TreeNode?) -> [Int] {var result = [Int]()        // 存储中序遍历结果var stack = [TreeNode]()    // 栈用于模拟递归var current = root          // 从根节点开始遍历// 当栈不为空或当前节点不为空时循环继续while current != nil || !stack.isEmpty {// 一直向左走，直到没有左子节点while let node = current {stack.append(node)  // 将当前节点压入栈current = node.left // 移动到左子节点}// 弹出栈顶节点并处理current = stack.removeLast() // 弹出栈顶result.append(current.val)   // 处理当前节点// 转向右子树current = current.right      // 移动到右子节点}return result
}// 示例用法：
// 构建一个示例二叉树
//      1
//     / \
//    2   3
//   / \
//  4   5let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)// 调用中序遍历函数
let result = inorderTraversal(root)
print(result)  // 输出: [4, 2, 5, 1, 3]