优享资讯 | Rust算法：用栈实现二叉树的迭代

掘金后端 ( ) • 2024-04-27 17:16

为什么用栈实现二叉树的迭代算法

用迭代法实现二叉树的同学，会发现使用迭代法实现先中后序遍历，很难写出统一的代码，不像是递归法，代码缝合简单统一，只需要稍微变更迭代的顺序，就可以实现对应的前中后序遍历，有没有一种方式，能让循环也可以实现一样的效果呢？

其实是有的：

思路是：模拟递归的底层代码，栈的实现，通过栈数据结构来实现循环迭代遍历二叉树。

听着有点可笑哈，因为有同学说，这不就是集齐了递归法栈溢出的缺点以及迭代法代码复杂的缺点了嘛？确实在一定程度上是这样的，但实际上还是稍微有点的，我们可以具体对比一下

递归中的栈溢出

在递归中，每个递归调用都会占用一定的调用栈空间，这部分空间用于保存函数参数、局部变量以及返回地址。在深度非常大的树或无限递归的情况下，递归可能会导致系统调用栈空间耗尽，从而引发栈溢出错误。这是因为大多数现代操作系统为每个线程分配的栈空间是有限的（例如，在许多系统中，默认可能是几百 KB 到几 MB）。

使用栈的迭代方法

在使用栈的迭代方法中，尽管也使用了栈结构，但这通常是程序数据区的一部分（例如，一个动态分配的栈），而不是操作系统管理的调用栈。这意味着它的限制更少，容量可以更大，通常由系统的整体内存限制来约束，而不是调用栈的限制。

栈溢出的可能性

递归：更容易受到系统调用栈大小限制的影响，因此在处理非常深的树时更容易发生栈溢出。
迭代：虽然理论上也可能因为栈数据结构过大而耗尽内存，但在实际应用中发生的可能性要小得多。因为迭代使用的栈是在堆上分配的，其限制通常远大于调用栈。

选择哪种方法

对于大多数日常应用，尤其是树的深度适中时，递归方法简洁直观。
对于深度非常大或未知的树结构，使用迭代方法可能更安全，以避免栈溢出的风险。

所以，从上面的分析可以看出，还是有一定意义在的，那话不多说，我们来看下具体是如何实现的吧

实现思路

使用一个简单的二叉树来说明这个迭代方法是如何使用栈来进行前序遍历的。假设我们有以下二叉树：

我们将按照前序遍历的顺序，即根节点 -> 左子树 -> 右子树，来遍历这棵树。

步骤和栈的变化

初始化栈：
- 将根节点（1）推入栈中。
- 栈内容：[1]
处理节点 1：
- 弹出节点 1，因为它是一个实际的节点，不是标记，所以我们检查它的子节点。
- 推入右子节点 3，然后左子节点 2，再推回节点 1，并在它之前加入 None 作为标记。
- 栈内容：[3, 2, 1, None]
处理标记 None 和节点 1：
- 弹出 None，然后弹出节点 1。将节点 1 的值添加到结果中。
- 栈内容：[3, 2]
- 结果：[1]
处理节点 2：
- 弹出节点 2，再次检查其子节点。
- 推入右子节点 5，左子节点 4，再推回节点 2，并加入 None 作为标记。
- 栈内容：[3, 5, 4, 2, None]
处理标记 None 和节点 2：
- 弹出 None，然后弹出节点 2。将节点 2 的值添加到结果中。
- 栈内容：[3, 5, 4]
- 结果：[1, 2]
处理节点 4：
- 弹出节点 4，检查它的子节点，因为它没有子节点，所以直接推回节点 4 和 None。
- 栈内容：[3, 5, 4, None]
处理标记 None 和节点 4：
- 弹出 None，然后弹出节点 4。将节点 4 的值添加到结果中。
- 栈内容：[3, 5]
- 结果：[1, 2, 4]
处理节点 5：
- 弹出节点 5，同样没有子节点，直接推回节点 5 和 None。
- 栈内容：[3, 5, None]
处理标记 None 和节点 5：
- 弹出 None，然后弹出节点 5。将节点 5 的值添加到结果中。
- 栈内容：[3]
- 结果：[1, 2, 4, 5]
处理节点 3：
- 弹出节点 3，检查它的子节点，没有子节点，直接推回节点 3 和 None。
- 栈内容：[3, None]
处理标记 None 和节点 3：
- 弹出 None，然后弹出节点 3。将节点 3 的值添加到结果中。
- 栈内容：[]
- 结果：[1, 2, 4, 5, 3]

最终结果

最终的前序遍历结果是 [1, 2, 4, 5, 3]，这恰好符合前序遍历的期望顺序。

这个方法通过在每个节点后面放置一个 None 标记来确保每个节点在正确的时间被处理，实现了没有递归的深度优先遍历。希望这个逐步示例能帮助您更好地理解这种迭代前序遍历的工作

Rust代码实现

    // 前序
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![];
        if root.is_some(){
            stack.push(root);
        }
        while !stack.is_empty(){
            if let Some(node) = stack.pop().unwrap(){
                if node.borrow().right.is_some(){
                    stack.push(node.borrow().right.clone());
                }
                if node.borrow().left.is_some(){
                    stack.push(node.borrow().left.clone());
                }
                stack.push(Some(node));
                stack.push(None);
            }else{
                res.push(stack.pop().unwrap().unwrap().borrow().val);
            }
        }
        res
    }
    // 中序
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![];
        if root.is_some() {
            stack.push(root);
        }
        while !stack.is_empty() {
            if let Some(node) = stack.pop().unwrap() {
                if node.borrow().right.is_some() {
                    stack.push(node.borrow().right.clone());
                }
                stack.push(Some(node.clone()));
                stack.push(None);
                if node.borrow().left.is_some() {
                    stack.push(node.borrow().left.clone());
                }
            } else {
                res.push(stack.pop().unwrap().unwrap().borrow().val);
            }
        }
        res
    }
    // 后序
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![];
        if root.is_some() {
            stack.push(root);
        }
        while !stack.is_empty() {
            if let Some(node) = stack.pop().unwrap() {
                stack.push(Some(node.clone()));
                stack.push(None);
                if node.borrow().right.is_some() {
                    stack.push(node.borrow().right.clone());
                }
                if node.borrow().left.is_some() {
                    stack.push(node.borrow().left.clone());
                }
            } else {
                res.push(stack.pop().unwrap().unwrap().borrow().val);
            }
        }
        res
    }

可以看到，通过栈结构实现的迭代方法，在面对前中后序不同的遍历方式时，只需要跟递归法一样，更改其中两行代码的顺序就可以实现不同的效果，总结，非常好用！

时间复杂度

遍历每个节点：在这种迭代方法中，每个节点都会被处理两次。首先，它被推入栈中作为一个实际的节点。第二次是当它和一个None标记一起被推回栈中，以便之后可以将其值添加到结果数组中。尽管节点被处理了两次，但每个节点的处理是常数时间的操作。

总体时间复杂度：由于树中的每个节点恰好被处理两次，并且处理每个节点的时间是常量的，因此总体时间复杂度为 O(n) ，其中 n 是树中节点的数量。这意味着算法的运行时间与树中的节点数成线性关系。

空间复杂度

栈的使用：这种方法的空间复杂度主要由栈的使用决定。在最坏的情况下（例如，树完全倾斜，形成一个链），栈可能需要存储几乎所有的节点。在最好的情况下（树是完全平衡的），栈的大小将是树的高度，即 O(log n) 。然而，由于需要为每个节点额外存储一个None标记，栈的最大大小可以达到 2n。

总体空间复杂度：因此，在任何情况下，空间复杂度最高可达到 O(n) ，其中 n 是树中的节点数。这种空间复杂度反映了最坏情况下的内存使用，即每个节点及其对应的None标记都需要在栈中占据空间。Pomelo_刘金。转载请注明原文链接。感谢！