二叉树的遍历

二叉树的遍历是一个面笔试高频考点，掌握它势在必得。

我于昨日刷到了一个中序遍历的题目，要是换做以前，我会直接扔个递归算法，牛客提交代码清脆的嘀嗒一声表示通过，好像还很开心的样子；其实，这是十分差劲的做法。刷一个题我们需要达到事半功倍的效果，而这就需要你有较强的思考能力与知识总结能力。

我于今日把二叉树前序、中序、后序遍历算法总结并实现了一遍，包括递归、迭代、Morris遍历法（我以前听过，但我唯唯诺诺，觉得它很难，直到今日我才将其弄懂。人总有这么一个心理，很倾向自己会的概念，惧怕生的、难度大的新兴事物）。

我以前序为参考，给出实现细节：

递归解决：

你和我肯定都觉得简单得一。对吗？

void preorder_recur(BinaryNode* root)
    {
        if (root)
        {
            printf("%d ", root->val);
            preorder_recur(root->left);
            preorder_recur(root->right);
        }
    }

根据递归公式：T(n) = 2T(n/2) + 1，可以得到时间复杂度为 O(n+logn)；空间复杂度借助于系统栈，系统栈需要记住每个结点的值，所以空间复杂度为 O(n)。

迭代解决：

迭代算法借助于数据结构栈，利用栈的FILO的特性，实现二叉树的遍历。

void preorder_iter(BinaryNode* root)
    {
        stack<BinaryNode *> s;
        while (root || !s.empty())
        {
            while (root)
            {
                printf("%d ", root->val);
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            root = root->right;
        }
    }

不管前中后序遍历，每个结点都需要进栈出栈一次，不过是处理方式细微的不同罢了，因此时间复杂度为 O(n)，空间复杂度也为 O(n)。

Morris遍历法：

morris 算法与前两种常规方法不同，它利用二叉树的叶结点的 right 指针域来保存后面将要访问的结点的信息，当这个 right 指针使用完了之后就把它置 NULL，但是再访问过程中有些结点会被访问两次，因此与递归的空间换时间策略不同，Morris 则是使用时间换空间的思想。

void preorder_morris(BinaryNode* root)
    {
        BinaryNode* temp = NULL;
        while (root)
        {
            if (root->left == NULL)
            {
                printf("%d ", root->val);
                root = root->right;
            }
            else     //找到左子树的最右子结点
            {
                temp = root->left;
                while (temp->right != NULL && temp->right != root)
                {
                    temp = temp->right;
                }
                if (temp->right == NULL)
                {
                    printf("%d ", root->val);
                    temp->right = root;
                    root = root->left;
                }
                else
                {
                    temp->right = NULL;
                    root = root->right;
                }
            }
        }
    }

强烈建议稿纸上走一遍流程。在整个遍历过程中，每个边最多访问了 2 次，而 n 个结点的二叉树有 n-1 条边，所以时间复杂度为 O(n)。并且使用了一个临时变量，所以空间复杂度为 O(1)。

与二叉树的递归遍历相比较，Morris遍历方法，每条边访问两次，比递归遍历过程访问次数多，虽然空间复杂度降低了，但是遍历的时间增加了，不过递归遍历也会有函数调用的开销。

其实，morris 遍历方法与线索二叉树雷同。在线索二叉树中，使用线索来保存节点的前驱和后继的信息，而这些线索是利用了叶节点的空指针域来保存的。在这里，使用叶子结点的右指针域来保存后面要访问的信息。

morris后序遍历和前中序遍历思想一致，但是有一点点小的不同，自己可以尝试予以实现。

PS：

1. 不知不觉十点半了，写到这里我又想起来还有个层序遍历了，层序遍历借助 queue 实现即可；
2. 实际上二叉树遍历的“递归算法”不就和无向图的“深度优先搜索”一样吗？“层序遍历”不就和“广度搜索”一样吗？
3. 知识联系起来可太多了，学是不可能学完了，还是先睡觉吧！