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

题目描述

使用迭代方法解题

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.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   5

let 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]

分析

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

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

理解递归和迭代的等效性

1. 递归调用栈：

   • 每次递归调用，系统会把当前函数的状态（变量、执行位置等）压入系统栈。
   • 当子任务完成后，系统会从栈中恢复上一次的状态继续执行。

2. 迭代模拟递归：

   • 我们需要手动管理一个栈，把当前节点和相关信息压入栈中。
   • 在处理子任务时，可以从栈中恢复之前的状态。

栈操作的核心逻辑

中序遍历的递归方式：

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

转换为迭代方式：

步骤详细解析

1. 初始化：

   • 使用一个栈来存储节点。
   • 使用一个变量 current 来追踪当前节点。

2. 模拟递归的左子树处理：

   • 不断将当前节点压入栈，并移向左子节点，直到当前节点为空。
   • 这一步类似递归调用到最左子节点的过程。

3. 处理节点并移向右子树：

   • 弹出栈顶节点，处理该节点（例如添加到结果数组中）。
   • 将 current 指向该节点的右子节点。

具体代码

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.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   5

let 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]

关键点总结

1. 模拟递归压栈：

   • 每次将当前节点压入栈中，然后移动到左子节点。
   • 这相当于递归调用处理左子树。

2. 模拟递归出栈：

   • 当无法继续向左走时，弹出栈顶节点。
   • 处理该节点后，转向右子树。

3. 继续遍历：

   • 将 current 指向右子节点，继续上述过程。

理解示例

对于二叉树：

     1
    / \
   2   3
  / \
 4   5

• 初始状态：
  • current 指向 1，stack 为空。
• 第一次内循环（处理左子树）：
  • 压入 1 -> 压入 2 -> 压入 4 -> 到达 nil。
• 第一次弹出：
  • 弹出 4，添加到结果：result = [4]，current 指向 nil。
• 第二次弹出：
  • 弹出 2，添加到结果：result = [4, 2]，current 指向 5。
• 处理 5：
  • 压入 5 -> 到达 nil -> 弹出 5，添加到结果：result = [4, 2, 5]。
• 处理 1：
  • 弹出 1，添加到结果：result = [4, 2, 5, 1]，current 指向 3。
• 处理 3：
  • 压入 3 -> 到达 nil -> 弹出 3，添加到结果：result = [4, 2, 5, 1, 3]。

---