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   5

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

代码解析

1. TreeNode 类：

   • TreeNode 类定义了一个二叉树节点，包括节点的值 val、左子节点 left 和右子节点 right。

2. inorderTraversal 方法：

   • 方法接受一个可选的 TreeNode 类型的参数 root，表示二叉树的根节点。
   • 定义一个数组 ret 来存储中序遍历的结果。

3. 递归函数 inorder：

   • inorder 函数接受一个可选的 TreeNode 作为参数，用于递归地进行中序遍历。
   • 使用 guard let 解包节点，如果节点为空则直接返回。
   • 递归调用 inorder 处理左子树。
   • 将当前节点的值添加到结果数组 ret 中。
   • 递归调用 inorder 处理右子树。

4. 调用递归函数：

   • 从根节点开始调用 inorder 函数，执行中序遍历。
   • 最后返回结果数组 ret。

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

复杂度分析

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

时间分析

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

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

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

空间分析

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

1. 递归调用栈空间：

   • 在最坏的情况下（即树的形态为单链表的情况下），递归调用栈的深度会达到树的高度。对于一个节点数为 n 的完全不平衡的树，高度为 n。
   • 对于平衡二叉树，树的高度为 log(n)，因此递归调用栈的最大深度为 log(n)。

2. 存储结果的数组：

   • 存储结果的数组 ret 需要存储树中所有节点的值，所以需要 O(n) 的空间。

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

• 在最坏情况下（完全不平衡的树），空间复杂度是 O(n)（栈空间 + 结果数组空间）。
• 在最佳情况下（完全平衡的树），空间复杂度是 O(n)（结果数组空间 + 栈空间为 O(log n)）。

总结：空间复杂度是 O(n)，因为结果数组的存储空间是 O(n)，且递归调用栈的空间在最坏情况下也是 O(n)。

进阶

递归算法很简单，你可以通过迭代算法完成吗？