递归实现
经典的二叉树三种遍历方式，主要是区分先中后三种顺序是怎样的顺序：“先中后”其实是描述根节点的位置顺序。然后在递归版本的实现里主要对应好打印语句出现的顺序即可。
struct TreeNode{
int m_value;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
void preOrder(TreeNode* pHead){
//先序遍历，根 - 左 - 右
if(pHead == NULL) return;
cout << pHead->m_value << endl; //当前节点在其左右子节点之前访问，根 - 左 - 右
preOrder(pHead->m_pLeft);
preOrder(pHead->m_pRight);
}
void inOrder(TreeNode* pHead){
//中序遍历，左 - 根 - 右
if(pHead == NULL) return;
inOrder(pHead->m_pLeft);
cout << pHead->m_value << endl;//当前节点在其左右子节点之间访问， 左 - 根 - 右
inOrder(pHead->m_pRight);
}
void posOrder(TreeNode* pHead){
//后序遍历，左 - 右 - 根
if(pHead == NULL) return;
posOrder(pHead->m_pLeft);
posOrder(pHead->m_pRight);
cout << pHead->m_value << endl;//当前节点在其左右子节点之后访问，左-右-根
}
非递归实现：使用栈辅助
先序遍历
- 申请一个栈，记为stack。将头结点head压入栈内。
- 从栈中弹出栈顶节点记为cur，并打印其值，同时将cur的非空的右、左子结点依次压入栈内。
- 一直重复步骤2，直到栈为空。
void preOrder(TreeNode* pHead){
//先序遍历，根 - 左 - 右
if(pHead == NULL) return;
stack<TreeNode*> nodes;
nodes.push(pHead);
while(!nodes.empty()){
TreeNode* cur = nodes.top();
nodes.pop();
cout << cur->m_value << endl;
if(cur->m_pRight) nodes.push(cur->m_pRight);
if(cur->m_pLeft) nodes.push(cur->m_pLeft);
}
}
中序遍历
- 申请一个栈，记为stack。开始时记节点cur = head。
- 将cur压入栈中，然后不断将cur的非空左子节点压入栈中。
- 若cur的所有左边界均已压入stack中，此时从stack中弹出栈顶节点node并打印，并令cur = node->right，继续2的过程。
- 当cur为空且stack为空时，停止。
void inOrder(TreeNode* pHead){
//中序遍历，左 - 根 - 右
TreeNode* cur = pHead;
stack<TreeNode*> nodes;
while(!nodes.empty() || cur){
while(cur){ //压入以cur为头节点的子树的左边界
nodes.push(cur);
cur = cur->m_pLeft;
}
cur = nodes.top();
nodes.pop();
cout << cur->m_value << endl;
cur = cur->m_pRight;
}
}
后序遍历
方法一：使用双栈
- 申请两个栈，记为stack1和stack2。首先将head压入栈stack1。
- 从stack1中弹出栈顶节点记为cur，压入stack2，并向stack1中依次压入cur的非空左、右子节点。
- 重复2过程直到stack1为空，然后依次从stack2中弹出栈顶元素并打印。
void posOrder1(TreeNode* pHead){
//后序遍历，左 - 右 - 根
if(pHead == NULL) return;
stack<TreeNode*> nodes1,nodes2;
nodes1.push(pHead);
while(!nodes1.empty()){
TreeNode* cur = nodes1.top();
nodes1.pop();
if(cur->m_pLeft) nodes1.push(cur->m_pLeft);
if(cur->m_pRight) nodes1.push(cur->m_pRight);
nodes2.push(cur);
}
while(!nodes2.empty()){
TreeNode* node = nodes2.top();
cout << node->m_value << endl;
nodes2.pop();
}
}
方法二：使用一个栈，分情况讨论
- 申请一个栈记为stack，开始时将头结点压入stack中。设置两个变量h和c，h表示最近一次弹出并打印的节点，c表示stack的栈顶节点。初始时，h为头节点，c为NULL。
- 每次令c等于当前stack的栈顶节点（先不弹出），此时分为三种情况：
① 若c的左孩子不为空，且h不等于c的左孩子也不等于右孩子，则把c的左孩子压入栈中。由于h的含义是最近一次弹出并打印的节点，若h等于c的左孩子或者右孩子，则说明c的左孩子已经打印完毕了，此时不再对其做操作，否则说明左孩子还没被处理，应该将左孩子压入栈中。
② 若条件①不成立，且c的右孩子不为空，h不等于c的右孩子，则把c的右孩子压入栈中。意义是若c的右孩子存在且h等于c的右孩子，则说明右孩子已经被打印过，此时不再对右孩子进行操作，否则将右孩子压入栈中。
③ 若条件①②均不成立，则说明c的左右孩子均已打印完毕，于是从stack中弹出c并打印，令h=c。 - 一直重复步骤2，直到stack为空。
void posOrder2(TreeNode* pHead){
//后序遍历，左 - 右 - 根
if(pHead == NULL) return;
stack<TreeNode*> nodes;
TreeNode* h = pHead;
nodes.push(pHead);
while(!nodes.empty()){
TreeNode* c = nodes.top();
if(c->m_pLeft && h != c->m_pLeft && h != c->m_pRight)
nodes.push(c->m_pLeft);
else if(c->m_pRight && h != c->m_pRight)
nodes.push(c->m_pRight);
else{
nodes.pop();
cout << c->m_value << endl;
h = c;
}
}
}
Morris遍历：空间复杂度为O(1)的神级遍历
以上使用的递归和非递归方法，都使用了O(logN)的额外空间，原因是普通的二叉树结构没有子节点回到父节点的指针，所以必须使用额外空间来记录上层结构以便从下层回到上层。
Morris遍历的实质是避免使用栈结构，而是让下层到上层有指针，具体是通过让底层节点的指向NULL的空闲指针指回上层的某个节点，从而完成下层到上层的移动。
Morris遍历规则
- 若当前节点无左子树，则遍历其右子树。
- 若当前节点有左子树，则找出其左子树的最右节点，若最右节点的right指向空则令其指向当前节点，然后继续向左遍历；若right指针指向当前节点，则令right指向空，再向右遍历。
二叉树示意图.png
按照Morris遍历规则来对上图的二叉树进行遍历：
①得到二叉树的根节点1，检查其左子树是否为空，左子树2存在则找到其最右节点5，并令5->right = 1，继续向左到达2（此时Morris序列为1-2）
②当前节点为2，其左子树4存在，且令最右节点(4)的right指向当前节点2，继续向左移动到达4（此时Morris序列为1-2-4）
③当前节点为4，没有左子树，则向右遍历到达2（此时Morris序列为1-2-4-2）
④当前节点为2，左子树的最右节点4的right指向自己则令其重新指向空，并向右移动到达5（此时Morris序列为1-2-4-2-5）
⑤当前节点为5，没有左子树，则向右遍历到达1（此时Morris序列为1-2-4-2-5-1）
⑥当前节点为1，左子树最右节点5的right指针指向自己则令其重新指向空，并向右移动到达3（此时Morris序列为1-2-4-2-5-1-3）
⑦当前节点为3，左子树存在，令其最右节点6的right指向当前节点3，继续向左移动到达6（此时Morris序列为1-2-4-2-5-1-3-6）
⑧当前节点为6，无左子树则向右到达3（此时Morris序列为1-2-4-2-5-1-3-6-3）
⑨当前节点为3，其左子树的最右节点指向自己则令其重新指向空，并向右移动到达7（此时Morris序列为1-2-4-2-5-1-3-6-3-7）
⑩当前节点为7，且无左右子树，遍历结束。
通过刚才的举例，发现Morris遍历的过程会经过有左子树的节点 两次，再观察Morris遍历的过程，第一次经过有左子树的节点时会通过其最右边界埋下返回上层的线索，才能够有第二次的回到父节点，第二次回到父节点时会认为已经对其左子树完成遍历并收回之前埋在左子树最右边界的线索。
那么如何把Morris遍历转换为我们常用的先中后序遍历呢？
Morris先序和中序遍历
在下面经典的递归遍历中，可以观察到整个过程有三次经过当前节点的行为，若将当前节点的打印行为放在1位置则为先序遍历，若打印行为放在2位置则为中序遍历，若打印行为放在3位置则为后序遍历。
void process(TreeNode* pHead){
if(pHead == NULL) return;
// 1
// cout << pHead->m_value << endl;
process(pHead->m_pLeft);
// 2
// cout << pHead->m_value << endl;
process(pHead->m_pRight);
// 3
// cout << pHead->m_value << endl;
}
而Morris遍历高度模仿了递归过程，可以经过当前节点最多两次。不难分析出，若将当前节点的打印行为放在第一次遍历时则为先序遍历，若将打印行为放在第二次遍历时则为中序遍历。代码如下：
void OrderMorris(TreeNode* pHead){
if(pHead == NULL) return;
TreeNode* pNode1 = pHead;
while(pNode1 != NULL){
TreeNode* pNode2 = pNode1->m_pLeft;
if(pNode2 == NULL){
// 1 & 2
// 注: 1位置表示先序遍历时打印行为发生的位置，2则表示中序遍历时打印行为发生的位置
// cout << pNode1->m_value << endl; //***打印行为***
// 若当前节点无左子树则只能遍历一次所以不论先序或中序都应该先打印该节点
pNode1 = pNode1->m_pRight;
}
else{
while(pNode2->m_pRight != NULL && pNode2->m_pRight != pNode1)
pNode2 = pNode2->m_pRight;
if(pNode2->m_pRight == NULL){
// 1 通过左子树最右节点的right指针是否指向当前节点来判断这是第几次经过当前节点，
// right指针指向空则说明这是第一次遍历该节点
// cout << pNode1->m_value << endl; //***打印行为***
pNode2->m_pRight = pNode1;
pNode1 = pNode1->m_pLeft;
}
else{
// 2 否则则说明这是第二次遍历该节点
// cout << pNode1->m_value << endl; //***打印行为***
pNode2->m_pRight = NULL;
pNode1 = pNode1->m_pRight;
}
}
}
}
Morris后序遍历
Morris遍历无法经过一个有左右孩子的节点三次，那如何能在遍历并打印其左右孩子之后再最后返回来打印父节点呢？——在第二次遍历有左孩子的节点时，依次逆序打印其左子树的右边界；且在最后（所有遍历完成之后），逆序打印整棵树的右边界。
二叉树示意图.png
上图中的二叉树的Morrios遍历序列为1-2-4-2-5-1-3-6-3-7。按照后续打印流程，应该是在第二次遍历2时，打印2的左子树右边界（4-），然后第二次遍历1时，打印1的左子树右边界（4-2-5-），第二次遍历3时，打印3的左子树右边界（4-2-5-6-），最后完成遍历之后打印（4-2-5-6-1-3-7）。从打印过程来看，每棵子树的右边界最多被遍历了二次，故整体的打印过程的时间复杂度还是O(N)。
下面来讨论一下边界打印的实现。首先确定的是，边界打印的行为发生在第二次经过某节点。然后，在不使用其他额外空间的情况下（保证Morris遍历的空间复杂度为O(1)）如何进行右边界的打印呢？
边界打印步骤.png
如上图所示，第二次遍历到节点1时，先把左子树的最右节点5的right指针指回空，并依次调整整条右边界使其逆序，如上图右。然后就可以从5节点开始依次打印整条边界，打印完成后再将整条边界逆序还原。
void printEdge(TreeNode* pHead){
TreeNode* pNode = pHead->m_pRight;
if(pNode == NULL){ //右边界只有一个节点
cout << pHead->m_value << endl;
}
else{ // 右边界有两个及两个以上的节点
// 第一次逆转
TreeNode* pPrev = pHead;
pPrev->m_pRight = NULL;
while(pNode != NULL){
TreeNode* pNext = pNode->m_pRight;
pNode->m_pRight = pPrev;
pPrev = pNode;
pNode = pNext;
}
// 逆序打印
pHead = pPrev;
while(pHead != NULL){
cout << pHead->m_value << endl;
pHead = pHead->m_pRight;
}
// 再次逆序还原
pHead = NULL;
pNode = pPrev;
while(pNode != NULL){
TreeNode* pNext = pNode->m_pRight;
pNode->m_pRight = pHead;
pHead = pNode;
pNode = pNext;
}
}
}
void posOrderMorris(TreeNode* pHead){
if(pHead == NULL) return;
TreeNode* pNode1 = pHead;
while(pNode1 != NULL){
TreeNode* pNode2 = pNode1->m_pLeft;
if(pNode2 == NULL){
pNode1 = pNode1->m_pRight;
}
else{
while(pNode2->m_pRight != NULL && pNode2->m_pRight != pNode1)
pNode2 = pNode2->m_pRight;
if(pNode2->m_pRight == NULL){
pNode2->m_pRight = pNode1;
pNode1 = pNode1->m_pLeft;
}
else{
pNode2->m_pRight = NULL;
// 在第二次遍历pNode1时，打印其左子树的右边界
printEdge(pNode1->m_pLeft);
pNode1 = pNode1->m_pRight;
}
}
}
// 遍历完成后，最后打印整棵树的右边界
printEdge(pHead);
}
