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]

分析

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

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

理解递归和迭代的等效性

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

栈操作的核心逻辑

中序遍历的递归方式：

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