树的遍历

前言

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

前提知识

• 二叉树有三种遍历方式：
  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<int> &res) {
        //递归退出条件，同时也是“商业程序员”以后工作要注意的错误排查
        if (root == nullptr) {
            return ;
        }
        res.push_back(root -> val);//输出当前节点的值，放第一行表示输出根节点
        preorder(root -> left, res);//遍历左子树
        preorder(root -> right, res);//遍历右子树
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        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<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> 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 遍历

遍历方法四 ———— 标记遍历法