二叉树的遍历是一个面笔试高频考点，掌握它势在必得。
我于昨日刷到了一个中序遍历的题目，要是换做以前，我会直接扔个递归算法，牛客提交代码清脆的嘀嗒一声表示通过，好像还很开心的样子；其实，这是十分差劲的做法。刷一个题我们需要达到事半功倍的效果，而这就需要你有较强的思考能力与知识总结能力。
我于今日把二叉树前序、中序、后序遍历算法总结并实现了一遍，包括递归、迭代、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：
- 不知不觉十点半了，写到这里我又想起来还有个层序遍历了，层序遍历借助 queue 实现即可；
- 实际上二叉树遍历的“递归算法”不就和无向图的“深度优先搜索”一样吗？“层序遍历”不就和“广度搜索”一样吗？
- 知识联系起来可太多了，学是不可能学完了，还是先睡觉吧！
