树的遍历

前言

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

前提知识

• 二叉树有三种遍历方式：
  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 图书馆四楼)

遍历方法三 ———— 标记遍历法

• 本着随便看看的心理，我在翻看题解的过程中发现了一位大佬惊为天人的思路，先附上大佬原话：

/*
在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。

栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成“一看就懂，一写就废”的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。

因此，我在这里介绍一种“颜色标记法”（瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。

其核心思想如下：

使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
(python实现)
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res
*/

• 只能大概看懂python的我一脸懵b又大受震撼，于是我在评论区找到了C++实现：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*, int> > stk;
        stk.push((make_pair(root, 0)));
        
        while(!stk.empty()) {
            auto [node, type] = stk.top();
            stk.pop();
            if(node == nullptr) continue;
            if(type == 0) {
                stk.push(make_pair(node->right, 0));
                stk.push(make_pair(node, 1));
                stk.push(make_pair(node->left, 0));
            }
            else result.emplace_back(node->val);
        }

        return result;

    }
};

• 评论区另一位大佬对这个方法进行了解读：本质是每个结点都要入栈两次后才能访问其元素值，第一次入栈是不能访问其值的，以为第一次入栈是第一次访问该节点，需要先访问该节点的左子树，这时会把该节点和左子树都入栈，同时第一次入栈时用0标记，第二次入栈时用1标记。当判断到栈顶元素标记为1时，证明是第二次入栈，就可以访问了。
• 这样看来，其实颜色标记法的本质就是标记，对某个元素的访问次数进行标记，达到访问次数就可以输出。
• 还有大佬进行优化，不需要额外的值来标记，只需要利用起来原本的TreeNode和int类型：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack,rst = [root],[]
        while stack:
            i = stack.pop()
            if isinstance(i,TreeNode):
                stack.extend([i.right,i.val,i.left])
            elif isinstance(i,int):
                rst.append(i)
        return rst

小结一下

• 学到这里我真的不得不感慨一下，有些人脑子是真的好使，能够深挖出问题和解决方法的本质，并且利用上现有资源去解决问题。

分隔栏：有点难不想学，这篇文章先更到这里。(2022.9.28 18:51 A3-404)

遍历方法四 ———— Morris遍历

• 先放个解析在这里：

/*
Morris遍历的详细解释+注释版

一些前置知识：

前驱节点，如果按照中序遍历访问树，访问的结果为ABC，则称A为B的前驱节点，B为C的前驱节点。
前驱节点pre是curr左子树的最右子树（按照中序遍历走一遍就知道了）。
由此可知，前驱节点的右子节点一定为空。
主要思想：

树的链接是单向的，从根节点出发，只有通往子节点的单向路程。

中序遍历迭代法的难点就在于，需要先访问当前节点的左子树，才能访问当前节点。

但是只有通往左子树的单向路程，而没有回程路，因此无法进行下去，除非用额外的数据结构记录下回程的路。

在这里可以利用当前节点的前驱节点，建立回程的路，也不需要消耗额外的空间。

根据前置知识的分析，当前节点的前驱节点的右子节点是为空的，因此可以用其保存回程的路。

但是要注意，这是建立在破坏了树的结构的基础上的，因此我们最后还有一步“消除链接”’的步骤，将树的结构还原。

重点过程： 当遍历到当前节点curr时，使用cuur的前驱节点pre

标记当前节点是否访问过
记录回溯到curr的路径（访问完pre以后，就应该访问curr了）
以下为我们访问curr节点需要做的事儿：

访问curr的节点时候，先找其前驱节点pre
找到前驱节点pre以后，我们根据其右指针的值，来判断curr的访问状态：
pre的右子节点为空，说明curr第一次访问，其左子树还没有访问，此时我们应该将其指向curr，并访问curr的左子树
pre的右子节点指向curr，那么说明这是第二次访问curr了，也就是说其左子树已经访问完了，此时将curr.val加入结果集中
更加细节的逻辑请参考代码：
*/

    public List<Integer> method3(TreeNode root) {
        List<Integer> ans=new LinkedList<>();
        while(root!=null){
            //没有左子树，直接访问该节点，再访问右子树
            if(root.left==null){
                ans.add(root.val);
                root=root.right;
            }else{
            //有左子树，找前驱节点，判断是第一次访问还是第二次访问
                TreeNode pre=root.left;
                while(pre.right!=null&&pre.right!=root)
                    pre=pre.right;
                //是第一次访问，访问左子树
                if(pre.right==null){
                    pre.right=root;
                    root=root.left;
                }
                //第二次访问了，那么应当消除链接
                //该节点访问完了，接下来应该访问其右子树
                else{
                    pre.right=null;
                    ans.add(root.val);
                    root=root.right;
                }
            }
        }
        return ans;
    }