Logo

菜单

发布于 2026-01-06 0 阅读
0

递归 vs 迭代：遍历树的 13 种方法。DEV 全球展示挑战赛，由 Mux 呈现：展示你的项目！

递归与迭代：遍历树的 13 种方法。

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

要理解递归，你必须先理解递归本身。我将展示 13 种不同的遍历树的方法，以此来比较递归实现和迭代实现。这样，我们就能一举两得：既理解递归，又理解数据结构和算法。

“糟糕的程序员只关心代码，优秀的程序员只关心数据结构及其相互关系。”

林纳斯·托瓦尔兹

递归、迭代以及如何遍历树都是很有用的技能，也是面试题中常见的内容。不要因为没花时间阅读一篇文章而错失下一次面试机会。

我假设您具备基本的编程技能，并且熟悉栈、队列、递归和循环。如果您觉得这太难，可以看看这篇文章，里面列出了一些入门资源。

对于每个问题，我都会提供 LeetCode 的链接，以便您可以尝试我的解决方案，或者用您喜欢的编程语言编写自己的解决方案。

我的代码示例将使用 C++。如果您不熟悉 API 或语法，没关系。我相信您能够理解其中的思路。这正是本文的目的。

什么是树？

N元树N元树

树是一种按层次结构组织数据的数据结构。它们从根节点递归定义，根节点包含需要存储的数据以及指向其子节点的指针。

有很多种树木非常适合特定的用途：

如果你不知道如何访问信息，那么存储信息就没有意义。

为简单起见，我将重点讨论二叉树。你需要将代码推广到每个节点最多有 N 个子节点的树。

我将向你展示13种遍历树的方法，并详细讨论它们。和往常一样，我会设置一些挑战题来巩固你的知识。我强烈建议你在阅读我的解答之前，先独立解决每个问题。

实践出真知，你会学到比阅读或观看多得多的东西。

穿越树木的13种方法

本节的大部分问题都将围绕二叉树展开。我们将节点定义如下：

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 }
Enter fullscreen mode Exit fullscreen mode

使用 astruct会默认将字段公开，这足以满足我们的需求。

为了进行复杂度分析，我们将假设我们将遍历一棵高度为H、包含N 个节点的树。

1. 前序遍历 - 递归

给定二叉树的根节点，返回其节点值的先序遍历结果。

前序遍历前序遍历

你可以在这里尝试解决这个问题。

解决方案

树的前序遍历、中序遍历和后序遍历，分别定义了我们访问树的根节点、左子节点和右子节点的顺序。前序遍历中的“前”指的是根节点。在前序遍历中，我们首先访问根节点，然后访问左子节点，最后访问右子节点。

你可以很轻松地将其转换为递归代码。你的函数将接收一个节点，从树的根节点开始。你需要定义：

  • 基本条件：只要节点不为空，
  • 递归关系：你处理它（例如，打印它的值），然后在左右子节点中调用相同的函数。

对于基本条件，你有两种选择。我在代码中将它们分别称为 A 和 B。在查看我的注释之前，请先查看代码，并尝试找出每种选择的优缺点。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        // helperB(root, sol);
        return sol;
    }

    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            sol.push_back(n->val);
            helperA(n->left, sol);
            helperA(n->right, sol);
        }
    }

    void helperB(TreeNode* n, vector<int>& sol){
        sol.push_back(n->val);
        if(n->left)
            helperB(n->left, sol);
        if(n->right)
            helperB(n->right, sol);
    }
};
Enter fullscreen mode Exit fullscreen mode

替代方案

  • 方案 A：每次函数调用都会检查接收到的节点是否为空。如果是，则会触发两次递归调用。此方案会导致栈空间增大。
  • 选项 B。该函数假定节点不为空。仅当左/右子节点不为空时，才会生成递归调用。该函数会执行更多 if 语句，但递归调用次数更少。

在没有更多上下文的情况下，这里没有绝对的对错之分。在面试中，最好讨论一下两种方案。这能体现你对代码的重视，以及你对代码潜在影响的思考。

你的首要任务应该是编写易读、易维护且运行正常的代码。只有当你对代码进行性能分析，并证实这些代码行对整体性能有显著影响时，才应该关注这些细节。不要凭空猜测。记住这一点。

“过早优化是万恶之源。”

唐纳德·克努斯

复杂

该算法访问每个节点一次，并将一个元素添加到向量的末尾，这部分工作量是常数——均摊后为零。因此，时间复杂度为 O(N)。

你能试着计算一下空间复杂度吗？试着把这个算法可视化到上面的树状图中。在“最坏情况”下，栈中会存储多少个节点？

我相信你已经找到了正确答案。你需要存储的最大节点数等于树的高度 H。因此，空间复杂度为 O(H)。

在接下来的问题中，我将向您展示同一算法的非递归实现，用于遍历树。但在此之前，我给您一个小挑战。

挑战

给定一棵 n 叉树，返回其节点值的先序遍历。

你可以在这里编写你的解决方案。

让你思考

这个问题很自然的后续问题是将其推广到具有 N 个子节点的树。在打开 LeetCode 链接之前，请先尝试自己对节点进行建模。以下是一些有趣的问题：

  • 哪些数据结构适合存储最多 N 个孩子？
  • 如果你不知道一个节点最多可以有多少个子节点，还能使用这种数据结构吗？还有其他什么选择？
  • 如果想要创建一个适用于不同数据类型的通用树该怎么办？这个问题的答案取决于你使用的编程语言：C++ 使用模板，Java 使用泛型等等。

目前，只需关注递归解法即可。即使“这很简单”，我们也看到，你仍然可以提出问题并讨论不同的替代方案。

2. 前序遍历 - 迭代

使用前序遍历遍历一棵树。不允许递归。

前序遍历

不妨在这里试试。

解决方案

现在我们将看到，递归并不是遍历树的唯一方法。

我们需要模拟使用递归函数时底层发生的一切。我们知道：

  • 首先，我们访问树的根节点——将其添加到解决方案中。
  • 然后我们处理左边的孩子，最后处理右边的孩子。
  • 我们需要自己创建和管理堆栈，而不是依赖递归调用。
  • 栈是一种后进先出的数据结构。因此，我们必须按照与提取顺序相反的顺序将元素压入栈中。

我们可以将这段描述转化为以下算法：

  1. 迭代算法首先将树的根节点添加到栈s中。
  2. 只要s不为空，我们就从中弹出元素。我们将这些元素添加到表示解决方案的数据结构中，因为我们希望先处理父节点，然后再处理其子节点。
  3. 我们将子节点推入s 中。先推右子节点，再推左子节点。这样，我们就能在弹出右子节点之前弹出左子节点，这正是我们想要的处理顺序。
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            auto t = s.top(); s.pop();
            sol.push_back(t->val);

            if(t->right)
                s.push(t->right);
            if(t->left)
                s.push(t->left);
        }
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

复杂度分析与递归版本相同。我们仍然需要访问 N 个节点，并且每个节点的工作量为常数。因此，时间复杂度为 O(N)。

就空间复杂度而言，栈最多需要存储与树的高度成正比的节点数，即 O(H)。

挑战

现在你需要将这个解决方案推广到包含 N 个节点的树上。你可以在这里测试你的解决方案。

3. 中序遍历 - 递归

给定二叉树的根节点，返回其节点值的中序遍历结果。

按顺序遍历按顺序遍历

不妨在这里试试。

解决方案

中序遍历是一种遍历树的方法，它首先访问左子节点，然后访问根节点，最后访问右子节点。在二叉搜索树（如上图所示）中，它会按照节点升序访问节点。

递归解法很简单。它与先序递归解法的唯一区别在于访问根节点和子节点的顺序。这只是一个很小的改动。不妨自己尝试实现一下。

我们之前讨论的关于额外 if 语句的所有内容都适用于这个问题，关于堆栈与内存的讨论也同样适用。这里提供一个与之前相同的解决方案，选项 A 和 B 也相同。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        //helperB(root, sol);
        return sol;
    }

    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            helperA(n->left, sol);
            sol.push_back(n->val);
            helperA(n->right, sol);
        }
    }

    void helperB(TreeNode* n, vector<int>& sol){
        if(n->left)
            helperB(n->left, sol);

        sol.push_back(n->val);

        if(n->right)
            helperB(n->right, sol);        
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

复杂度分析与之前的递归示例相同。我们做的完全一样，只是顺序不同。

4. 按顺序遍历 - 迭代

使用中序遍历方法遍历一棵树。不允许递归。

按顺序遍历

在这里测试你的解决方案。

解决方案

我知道你在想什么。你说得对，我们需要一个堆栈。

让我们可视化一下前面那棵树的中序遍历过程。

  • 我们在根节点上调用辅助函数。
  • 这会调用根节点的左子节点。
  • 这会调用根的左子节点的左子节点。
  • 这种遍历左子节点的过程会一直重复，直到遇到没有左子节点的节点k。只有当节点k没有左子节点时，我们才会继续遍历它的右子节点。
  • 隐式栈存储了根节点和 k 节点之间的所有节点。处理完 k 的右子节点后，下一个要处理的节点将从隐式栈中提取出来。

我们需要用我们的栈来模拟这个。我们称它为s。

  1. 为了开始遍历树，我们将树的根节点添加到 s 中。
  2. 如果根节点没有左子节点，或者我们已经探索完了根节点的左子树，我们就处理根节点并移动到它的右子节点。
  3. 否则，我们就继续向左移动：
    1. 我们将根节点添加到栈中，以便稍后处理。
    2. 我们向左移动

从这个算法来看，我们需要一个栈和一个指针 n来标记当前所在的节点。如果 n 为空，则表示我们已经探索完一个子树，需要查询栈以获取下一个要处理的节点。如果栈为空，则表示我们已经处理完所有节点。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        stack<TreeNode*> s;
        TreeNode* n = root;
        while(n || !s.empty()) {
            const bool hasToGoRight = !n;
            if(hasToGoRight){
                auto top = s.top(); s.pop();
                sol.push_back(top->val);
                n = top->right;
            } else {
                s.push(n);
                n = n->left;
            }
        }
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

复杂度分析与之前完全相同：时间复杂度为 O(N)，空间复杂度为 O(H)。

5. 后序遍历 - 递归

给定二叉树的根节点，返回其所有节点值的后序遍历结果。

后序遍历

请在此处检查您的实现。

解决方案

在后序遍历中，我们首先访问左子节点，然后访问末子节点，最后访问树的根节点，因此得名“后序”。该算法与我们刚才看到的先序遍历和中序遍历相比，只需进行极小的改动。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        //helperB(root, sol);
        return sol;
    }

    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            helperA(n->left, sol);
            helperA(n->right, sol);
            sol.push_back(n->val);
        }
    }

    void helperB(TreeNode* n, vector<int>& sol){
        if(n->left)
            helperB(n->left, sol);
        if(n->right)
            helperB(n->right, sol);        
        sol.push_back(n->val);
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

与预购和在售订单相同。

挑战

尝试将此方法推广到 N 个节点的情况。请在此处编写您的解决方案。

6. 后序遍历 - 迭代

使用后序遍历遍历二叉树。不允许递归。

后序遍历

请在这里尝试你的解决方案。

解决方案

如果你认为我们又需要堆栈了，那么你是对的。

我熟悉基于单个栈的相对复杂的解决方案。这个解决方案可以用两个栈实现，或者只需要一个栈和一个向量。这可以通过使用第二个栈来实现。空间复杂度仍然是 O(N)。

如果你还记得的话，在迭代前序遍历中，我们先将根节点添加到解中，然后再将左右子节点压入。我知道这有点突兀，但我们来看看如果先压入左子节点，再压入右子节点会发生什么。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        stack<TreeNode*> s;
        s.push(root);
        vector<int> sol;
        while(!s.empty()){
            auto top = s.top(); s.pop();

            sol.push_back(top->val);

            if(top->left)
                s.push(top->left);
            if(top->right)
                s.push(top->right);
        }

        for(auto x : sol)
          cout<<x<<endl;
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

您可以验证我们得到 [18, 21, 22, 20, 16]，这与反转这棵树的前序遍历结果 [16, 20, 22, 21, 18] 相同。我们只需要在算法末尾添加一个额外的步骤来反转解决方案——或者使用两个栈。

我对这个算法没有直觉。我必须承认，我不得不上网查找这个解决方案，因为我不想提出更复杂的替代方案。

最重要的是，值得注意的是，有时研究类似的问题有助于找到解决你正在尝试解决的问题的方法。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        stack<TreeNode*> s;
        s.push(root);
        vector<int> sol;
        while(!s.empty()){
            auto top = s.top(); s.pop();

            sol.push_back(top->val);

            if(top->left)
                s.push(top->left);
            if(top->right)
                s.push(top->right);
        }

        reverse(sol.begin(), sol.end());        
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

这种复杂性在时间和空间上都是线性的：

  • 时间复杂度：每个元素所需的时间复杂度是恒定的。反转向量也是一个线性时间操作。
  • 空间：空间复杂度是线性的，无论我们使用一个栈还是两个栈。

7. Morris遍历——如何使用恒定空间遍历树

使用前序遍历和中序遍历遍历一棵树。空间复杂度必须为 O(1)——不能使用递归，也不能使用任何数据结构来存储节点信息。

解决方案

你说得对。你仍然需要存储一些关于节点的信息才能访问它们。这个算法修改了节点，使其能够在无需显式数据结构的情况下遍历树。算法结束后，节点会恢复到初始状态。

我们先重点讨论中序遍历。前序遍历只需要稍作修改。

我们将有两个指针：current和explorer。我们将使用explorer在树中移动，并从一些叶子节点建立指向current 的链接。current只有在之前已经从其前驱节点建立指向 current 的链接后才能向左移动。这是我唯一“记住”的 Morris 算法的内容。有了这些，我每次都可以画出树并重新构建算法。

这张图包含了我们搭建桥梁所需的所有连接。但是，我们不需要保留任何连接：一旦使用完毕，我们就拆除桥梁。

莫里斯遍历

算法如下：

  1. 首先，我们将当前用户设置为 root。
  2. 如果当前节点 没有左子节点，则将当前节点添加到解中，并移动到其右子节点。
  3. 否则：
    1. 我们使用 *explorer 找到curren*t 的前身。
    2. 如果explorer和current之间已经存在链接，我们会断开该链接，将current添加到解决方案中，并移动到current 的右子元素。
    3. 否则，我们将explorer和current之间建立链接，并将current移到它的左子节点。
  4. 返回步骤 2，直到*当前* 变为空。

例子

让我们逐步对上面的树运行该算法：

  • 电流从7开始。
  • 使用资源管理器，我们找到了它的前身 6，并将其与当前版本关联起来。
  • 我们将电流调至 4。
  • 使用资源管理器，我们找到了它的前身 4，并将其与当前版本关联起来。
  • 我们将电流移至 2。
  • Current 没有左子，因此我们的解决方案变为：[2]。
  • 我们向电流的右侧移动，4。
  • 使用资源管理器，我们找到了它的前身，即 2。
  • 由于 explorer (2) 已经链接到 current (4)，我们断开此链接并将 4 添加到我们的解决方案中：[2, 4]
  • 我们将电流转移到它的右子节点，即 5。
  • 当前节点没有左子节点，因此我们将其添加到我们的解 [2, 4, 5] 中，并移动到其右子节点。
  • 我们与步骤 9 的情况相同。我们的解变为 [2, 4, 5, 6]，电流又回到了 7。
  • ETC。

这是我用 C++ 实现的该算法。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> sol;
        auto current = root;
        while(current){
            if(!current->left) {
                sol.push_back(current->val);
                current = current->right;
            } else {
                TreeNode* explorer = current->left;
              //Find currents predecessor
                while(explorer->right && explorer->right != current) {
                    explorer = explorer->right;
                }

              //Is it linking back to current?
                if(explorer->right == current) {
                    explorer->right = nullptr;
                    sol.push_back(current->val);
                    current = current->right;
                } else {
                    explorer->right = current;
                    current = current->left;
                }
            }
        }
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

序贯和先序的区别在于最后一个代码块，它检查是否存在现有链接。我们只需要移动将当前值添加到解决方案中的那行代码即可。

预购：

//Is it linking back to current?
if(explorer->right == current) {
  explorer->right = nullptr;
  current = current->right;
} else {
  sol.push_back(current->val);
  explorer->right = current;
  current = current->left;
}
Enter fullscreen mode Exit fullscreen mode

Morris 后序遍历有点复杂，所以我就不在本部分讨论它了。

复杂

时间复杂度的问题留给你们自己研究。

空间复杂度为 O(1)。虽然由于我们修改了树结构，实际上使用了更多空间，但严格来说，执行此算法并不需要额外的空间。

挑战

你能找出这个算法可能存在的问题吗？例如，如果多个线程需要对同一棵树执行此算法，会发生什么情况？

8. 层序遍历 - 迭代

给定一棵二叉树，返回其节点值的层序遍历结果。（即，从左到右，逐层遍历）。

层序遍历

对于这棵树，解决方案如下：[[15], [10, 21], [5, 20, 23], [6]].

请尝试在这里解决这个问题。

解决方案

这次我将从迭代法入手，因为我觉得它更容易编写代码。我们可以用广度优先搜索（BFS）来解决这个问题。唯一的难点在于如何判断何时开始新的一轮搜索。我们可以通过两种方式来实现：

  • 在推送完一个层级中的所有节点后，我们会引入一种特殊类型的节点，表示我们需要一个新的层级——例如，nullptr。
  • 在开始处理队列之前，我们先记录队列的大小 s，即该层级的元素数量。处理完s 个元素后，我们创建一个新的层级。

这里我采用了第二种方法。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int size = q.size();
            vector<int> partial;
            while(size-->0){
                auto n = q.front();
                partial.push_back({n->val});
                q.pop();
                if(n->left)
                    q.push({n->left});
                if(n->right)
                    q.push({n->right});
            }
            sol.push_back(partial);
        }
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

我们访问 N 个节点，每个节点的工作量为常数。换句话说，这种方法的时间复杂度为 O(N)。

空间复杂度取决于队列的最大容量。由于我们按层存储元素，因此它是树宽度的函数。

对于高度为 H 的满树（除叶节点外，每个节点都有两个子节点），每一层节点数的最大值出现在最后一层（叶节点），即 2^H。对于这种类型的树，H = log2(N)。

总之，空间复杂度也是 O(N)。

挑战

尝试解决这个变体问题。

9. 层序遍历 - 递归

给定一棵二叉树，返回其节点值的层序遍历结果。（即，从左到右，逐层遍历）。

层序遍历

对于这棵树，解决方案如下：[[15], [10, 21], [5, 20, 23], [6]].

请尝试解决这里的问题。

解决方案

始终牢记遍历树的三种基本方法：前序遍历、中序遍历和后序遍历。这个问题实际上是前序遍历树的一种变体。

唯一需要注意的是，你需要将深度相同的节点放在一起。这可以通过使用一个变量来跟踪你当前探索的层级轻松实现。

使用哈希表，您可以将处理的每个节点存储在正确的深度。由于我们首先探索左子节点，因此每一层元素的相对顺序都会被保留下来。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};

        //Here is where the magic happens
        map<int, vector<int>> levels;
        helper(root, levels);

        //Here we create the solution in the expected data structure
        vector<vector<int>> sol;
        for(auto it = levels.begin(); it != levels.end(); ++it){
          sol.push_back(it->second);
        }
        return sol;
    }

    void helper (TreeNode* n, map<int, vector<int>> &levels, int depth = 0){
        levels[depth].push_back(n->val);

        if(n->left)
            helper(n->left, levels, depth + 1);

        if(n->right)
            helper(n->right, levels, depth + 1);
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

我们访问 N 个节点，每个节点的工作量是恒定的（向哈希表中添加元素的均摊时间是恒定的）。因此，时间复杂度为 O(N)。

此实现方式将所有节点存储在哈希表中。因此，空间复杂度为 O(N)。

10. 层序之字形遍历

给定一棵二叉树，返回其节点值的之字形层序遍历结果。（即，从左到右遍历下一层，然后从右到左遍历下一层，如此交替进行）。

层序之字形遍历用于层级顺序之字形遍历的树

对于这棵树，解决方案看起来像 [[8], [14, 4], [2, 5,12,19]].

不妨在这里试试。

解决方案

这个问题乍一看可能有点棘手，但你拥有解决它的工具。上面提到的一个问题与此非常相似。我给你一分钟时间找到它。

你说得对。这是一个层序遍历。唯一不同之处在于，有些层需要从左到右处理，有些层需要从右到左处理。我们可以使用两个栈 s1 和 s2 轻松实现这一点。

假设我们已经从左到右完成了一层。我们压入栈 s1 的最后一个元素将是树中该层最右边的元素。

  1. 首先，我们创建一个新的局部解决方案——新关卡的解决方案。
  2. 我们将栈 s1 弹出，并将该元素添加到部分解决方案中。
  3. 下一层将从右向左探索。因此，我们首先将左子节点和右子节点添加到另一个栈 s2 中。
  4. 我们持续处理 s1 中的元素，直到 s1 为空为止。
  5. 在下一次迭代中，我们将处理 s2 中的元素，从左到右完成下一级别。
  6. 当我们处理 s2 中的节点时，我们首先添加它们的右子节点，然后添加它们的左子节点 - 后进先出 (LIFO) 到下一层。
  7. 我们重复此操作，直到两个堆栈都为空为止。
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(root);
        while(!s1.empty() || !s2.empty()){
            vector<int> partial;
            while(!s1.empty()){
                auto top = s1.top();
                partial.emplace_back(top->val);
                s1.pop();
                if(top->left)
                    s2.push(top->left);
                if(top->right)
                    s2.push(top->right);
            }
            if(!partial.empty()){
                sol.push_back(partial);
                partial.clear();
            }
            while(!s2.empty()){
                auto top = s2.top();
                partial.emplace_back(top->val);
                s2.pop();
                if(top->right)
                    s1.push(top->right);
                if(top->left)
                    s1.push(top->left);
            }
            if(!partial.empty()){
                sol.push_back(partial);
            }
        }
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

时间和空间复杂度都是线性的。你能看出为什么吗？

挑战

这里我提供了几个该问题的变体供你练习：

11. 树的侧视图

给定一棵二叉树，想象自己站在它的右侧，返回你从上到下可以看到的所有节点的值。

树的侧视图

这棵树的解是 [16, 19, 18, 13]。从右侧看，你看不到其他节点，因为解中的节点“挡住了它们的视线”。

请尝试在这里编写代码。

解决方案

这看起来可能有点棘手，但你拥有解决它所需的工具。你需要打印出每一层最右边的节点。之前的一些问题与此题非常相似。

你可以通过修改层级遍历，只打印每一层的最后一个节点来解决这个问题。

这是其中一种可能的实现方式。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> sol;
        while(!q.empty()){
            int size = q.size();
            for(int i = 1; i <= size; ++i){
                auto top = q.front();
                if(i == size){
                    sol.push_back(top->val);
                }
                if(top->left)
                    q.push(top->left);
                if(top->right)
                    q.push(top->right);
                q.pop();
            }
        }
        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

分析方法与层序遍历相同。

挑战

您可以尝试以下两种方法：

  • 递归地解决这个问题
  • 打印左侧而不是右侧
  • 打印叶子

12. 垂直顺序遍历 - 递归

给定一棵二叉树，返回其节点值的垂直顺序遍历。

对于位置 的每个节点(X, Y)，其左子节点和右子节点分别位于位置(X-1, Y-1)和(X+1, Y-1)。

X = -infinity从到 画一条垂直线X = +infinity，每当垂直线与某些节点相交时，我们就按从上到下（Y坐标递减）的顺序报告节点的值。

如果两个节点的位置相同，则先报告的节点的值是较小的值。

返回一个按坐标顺序排列的非空报告列表X。每个报告都包含一个节点值列表。

垂直顺序横断面

本例的解为 [[4], [6], [12], [21, 14, 23], [20], [24], [25]].

请在此处编写您的解决方案。

解决方案

我敢肯定你已经找到解决方案了。

每次向左或向右移动时，都可以记录 X 坐标。这很容易用递归实现。每次向左移动到左侧节点，X 坐标减 1；向右移动，X 坐标加 1。

使用哈希表，您可以存储位于特定 X 位置的所有节点，从而构建解决方案。

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root)
        return {};

        map<int, vector<pair<int, int>>> distances;
        helper(root, 0, 0, distances);

        vector<vector<int>> sol;
        for(auto x : distances){
          //Using a lambda function to ensure nodes appear in the expected order
            sort(x.second.begin(),
                 x.second.end(), 
                 [] (pair<int,int> &a, pair<int,int> &b) {
                    if(a.first==b.first)
                        return a.second<b.second;
                    else
                        return a.first<b.first;
                    }
                );
            vector<int> v;
            for(auto y : x.second){
                v.push_back(y.second);
            }
            sol.push_back(v);
        }
        return sol;
    }

  void helper(TreeNode* root, int hd, int c, map<int,vector<pair<int,int>>> &distances){
        if(!root)
            return;
        distances[hd].push_back({c, root->val});

        helper(root->left, hd-1, c+1, distances);
        helper(root->right, hd+1, c+1, distances);
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

我们访问每个节点一次，每个节点的工作量恒定。然而，在最后一步，我们需要对每一层的节点进行排序，这会增加复杂度。计算这个新的复杂度并非易事，但显然它被限制在 O(NLogN) 以内。

由于我们将所有节点存储在哈希表中，因此空间复杂度为 O(N)。

13. 垂直顺序遍历 - 迭代

给定一棵二叉树，返回其节点值的垂直顺序遍历。

对于位置 的每个节点(X, Y)，其左子节点和右子节点分别位于位置(X-1, Y-1)和(X+1, Y-1)。

X = -infinity从到 画一条垂直线X = +infinity，每当垂直线与某些节点相交时，我们就按从上到下（Y坐标递减）的顺序报告节点的值。

如果两个节点的位置相同，则先报告的节点的值是较小的值。

返回一个按坐标顺序排列的非空报告列表X。每个报告都包含一个节点值列表。

垂直树遍历

本例的解为 [[4], [6], [12], [21, 14, 23], [20], [24], [25]].

在这里测试你的解决方案。

解决方案

根据我对上一个问题的解释以及你对广度优先搜索的理解，你将能够编写出解决该问题的迭代算法版本。

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int,int>>> distances;
        queue<pair<TreeNode*, int>> q;
        int level = 0;
        q.push({root, 0});
        distances[0].push_back({level, root->val});

        while(!q.empty()) {
            const int size = q.size();
            level++;
            for(int i = 0; i < size; i++) {
                auto node = q.front().first;
                int sd = q.front().second; q.pop();

                if(node->left) {
                    distances[sd-1].push_back({level, node->left->val});
                    q.push({node->left,sd-1});
                }

                if(node->right) {
                    distances[sd+1].push_back({level, node->right->val});
                    q.push({node->right,sd+1});
                }
            }
        }

        vector<vector<int>> sol;
        for(auto it : distances) {
            vector<int> partial;
            sort(it.second.begin(), it.second.end());

            for(int i= 0; i < it.second.size(); i++) {
                partial.push_back(it.second[i].second);
            }
            sol.push_back(partial);
        }

        return sol;
    }
};
Enter fullscreen mode Exit fullscreen mode

复杂

这道题留给你们自己练习。如果需要提示，可以参考前面的题目。

结论

这篇文章原本是要讲解如何遍历树的，结果却变成了研究同一问题的递归和迭代解决方案的契机。我们可以从中总结出一些经验：

  • 一般来说，将递归算法转换为迭代算法并非易事。然而，对于尾递归函数来说，这却非常简单。
  • 递归解法可能导致堆栈溢出。请始终考虑迭代解法（但需受内存大小限制）。
  • 有些问题可以用递归直接解决，而有些问题则需要复杂的迭代实现。
  • 递归解决方案由于栈调用而往往速度较慢。然而，你的重点应该放在编写可维护、易读且能正常运行的代码上。只有在使用性能分析器找到真正的瓶颈之后，才应该进行优化。

正如我之前所说，关键不在于解决一百万个问题或花费一百万个小时，而在于你从每个小时中获得了什么。我们也看到，即使是看似简单的问题，我们也能从中挖掘出很多东西。

“只要我们能真正着手解决，就没有太小或太琐碎的问题。”

理查德·费曼

本文旨在引发您对每个问题的思考。我们已经了解了遍历树的 13 种方法，并探讨了递归和迭代的实现方式。通过阅读本文，您肯定有所收获。接下来，我邀请您阅读我关于动态规划的文章。

如果您觉得这篇文章对您有帮助，请分享。相信会有更多人从中受益。您的分享可以帮助他人通过考试、求职面试，或者解决工作中的难题。

欢迎访问我的博客www.yourdevopsguy.com ，并在Twitter上关注我。

文章来源：https://dev.to/codinglanguages/recursion-vs-iteration-13-ways-to-traverse-a-tree-2n89
🔥我们精选的 13 款 Kube...
JavaScript 数组系列讲解...