树的遍历前言

  • 在一个平常的星期二下午，一节数据结构课中，想着做点什么的我，打开了力扣。正好老师在讲树，我也从二叉树最基础的遍历开始刷题，没想到打开了新世界的大门······

前提知识

  • 二叉树有三种遍历方式：
    1. 前序遍历(根节点 -> 左子树 -> 右子树)
    2. 中序遍历(左子树 -> 根节点 -> 右子树)
    3. 后序遍历(左子树 -> 右子树 -> 根节点)
  • 可以看出这三种遍历方式的特点：
    1. 前/中/后，代表着根节点的遍历顺序
    2. 左子树一定比右子树先访问到

遍历方法一 ———— 递归

  • 用当时老师的话来说就是：三行代码的事
  • 至于哪三行，话不多说，上代码：
//LeetCode 144. 二叉树的前序遍历/** * Definition for a binary tree node. * 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) {} * }; */class Solution {public:    void preorder(TreeNode* root, vector &res) {        //递归退出条件，同时也是“商业程序员”以后工作要注意的错误排查        if (root == nullptr) {            return ;        }        res.push_back(root -> val);//输出当前节点的值，放第一行表示输出根节点        preorder(root -> left, res);//遍历左子树        preorder(root -> right, res);//遍历右子树    }    vector preorderTraversal(TreeNode* root) {        vectorres;        preorder(root, res);        return res;    }};//时间复杂度：O(n)O(n)，其中 nn 是二叉树的节点数。每一个节点恰好被遍历一次。//空间复杂度：O(n)O(n)，为递归过程中栈的开销，平均情况下为 O(\log n)O(logn)，最坏情况下树呈现链状，为 O(n)O(n)。
  • 同理，若想使用中/后序遍历，只需将res.push_back(root -> val);放在第二/第三行即可

遍历方法二 ———— 迭代

  • 由之前的刷题经验可知，很多能用递归实现的方法也可以用迭代实现，在此处也是可以的，只不过迭代会比递归更难理解一些

深入底层

  • 为什么能用递归实现的时候，也能用迭代实现呢？我们不妨想想递归实现的底层原理是什么。递归实现遍历本质上是函数不断调用自身，但通过改变传入形参来不断递进的过程。在这个过程中，递归隐式地维护了一个栈：调用preorder并让其入栈，左子树走到底之后就将元素弹出(输出元素)，然后遍历右子树。由于这个过程太隐蔽了(都是程序运行时内部完成的)，我们就看不到递归背后的运行情况是怎么样的(这可能也是递归难以理解的原因之一)。而迭代其实就是将这个过程展现出来，显式地维护这个栈，完成计算机底层实现的操作，以下是代码：
class Solution {public:    vector preorderTraversal(TreeNode* root) {        vector res;        if (root == nullptr) {            return res;        }        stack stk;        TreeNode* node = root;        while (!stk.empty() || node != nullptr) {            while (node != nullptr) {                res.emplace_back(node->val);//前序遍历，先将根节点输出                stk.emplace(node);                node = node->left;            }            node = stk.top();            stk.pop();            node = node->right;        }        return res;    }};
  • 一般都是递归比迭代难理解，但这里似乎是个反例，迭代的代码比递归的更复杂难懂一些，但仔细看会发现和递归其实是一样的，中/后序遍历也只需要简单调整代码逻辑顺序就可以了。

分隔栏：偷个懒下次继续写,该去学java了(2022.9.27 19:28)遍历方法三 ———— Morris 遍历遍历方法四 ———— 标记遍历法