94. 二叉树的中序遍历 (Swift版本, 递归)

题目描述

在这里插入图片描述

使用递归方法解题

使用了一个递归函数 inorder 来进行二叉树的中序遍历，并将结果存储在数组 ret 中

/*** Definition for a binary tree node.* public class TreeNode {*     public var val: Int*     public var left: TreeNode?*     public var right: TreeNode?*     public init() { self.val = 0; self.left = nil; self.right = nil; }*     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }*     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {*         self.val = val*         self.left = left*         self.right = right*     }* }*/
class Solution {func inorderTraversal(_ root: TreeNode?) -> [Int] {var ret = [Int]()// 递归函数进行中序遍历func inorder(_ root: TreeNode?) {guard let root = root else {return}inorder(root.left)        // 递归处理左子树ret.append(root.val)      // 访问当前节点inorder(root.right)       // 递归处理右子树}// 从根节点开始中序遍历inorder(root)// 返回遍历结果return ret}
}

示例用法

// 构建一个示例二叉树
//      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 solution = Solution()
let result = solution.inorderTraversal(root)
print(result)  // 输出: [4, 2, 5, 1, 3]

代码解析

TreeNode 类：
- TreeNode 类定义了一个二叉树节点，包括节点的值 val、左子节点 left 和右子节点 right。
inorderTraversal 方法：
- 方法接受一个可选的 TreeNode 类型的参数 root，表示二叉树的根节点。
- 定义一个数组 ret 来存储中序遍历的结果。
递归函数 inorder：
- inorder 函数接受一个可选的 TreeNode 作为参数，用于递归地进行中序遍历。
- 使用 guard let 解包节点，如果节点为空则直接返回。
- 递归调用 inorder 处理左子树。
- 将当前节点的值添加到结果数组 ret 中。
- 递归调用 inorder 处理右子树。
调用递归函数：
- 从根节点开始调用 inorder 函数，执行中序遍历。
- 最后返回结果数组 ret。

这个实现清晰且符合中序遍历的定义，对于二叉树的遍历操作非常适用。如果你有任何其他问题或需要进一步的解释，请告诉我。

复杂度分析

时间复杂度：O(n)，因为每个节点被访问一次。
空间复杂度：O(n)，由于结果数组需要 O(n) 的空间以及递归调用栈在最坏情况下也需要 O(n) 的空间。

时间分析

对于二叉树的中序遍历，算法需要访问每个节点恰好一次。

每个节点访问一次：在遍历过程中，每个节点被递归地访问一次。因此，时间复杂度是 O(n)，其中 n 是树中节点的数量。

总结：时间复杂度是 O(n)。

空间分析

空间复杂度主要由递归调用的栈空间和存储结果的数组空间构成。

递归调用栈空间：
- 在最坏的情况下（即树的形态为单链表的情况下），递归调用栈的深度会达到树的高度。对于一个节点数为 n 的完全不平衡的树，高度为 n。
- 对于平衡二叉树，树的高度为 log(n)，因此递归调用栈的最大深度为 log(n)。
存储结果的数组：
- 存储结果的数组 ret 需要存储树中所有节点的值，所以需要 O(n) 的空间。

综合考虑两部分的空间复杂度：