前中后遍历 递归版
1 /* Recursive solution */ 2 class Solution { 3 public: 4 vector preorderTraversal(TreeNode *root) { 5 6 vector result; 7 preorderTraversal(root, result); 8 9 return result;10 }11 12 void preorderTraversal(TreeNode *root, vector & result)13 {14 if(root == NULL) return;15 result.push_back(root->val);16 17 preorderTraversal(root->left, result);18 preorderTraversal(root->right, result);19 }20 21 };
1 /* Recursive solution */ 2 class Solution { 3 public: 4 vector inorderTraversal(TreeNode *root) { 5 6 vector result; 7 inorderTraversal(root, result); 8 9 return result;10 }11 12 void inorderTraversal(TreeNode *root, vector & result)13 {14 if(root == NULL) return;15 16 inorderTraversal(root->left, result);17 result.push_back(root->val);18 inorderTraversal(root->right, result);19 }20 21 };
1 /* Recursive solution */ 2 class Solution { 3 public: 4 vector postorderTraversal(TreeNode *root) { 5 6 vector result; 7 postorderTraversal(root, result); 8 9 return result;10 }11 12 void postorderTraversal(TreeNode *root, vector & result)13 {14 if(root == NULL) return;15 16 postorderTraversal(root->left, result);17 result.push_back(root->val);18 postorderTraversal(root->right, result);19 }20 21 }; 下面是迭代版本
1 preorder： 节点入栈一次， 入栈之前访问。
2 inorder：节点入栈一次，出栈之后访问。
3 postorder：节点入栈2次，第二次出战后访问。
1 class Solution { 2 public: 3 vector preorderTraversal(TreeNode *root) { 4 5 vector result; 6 stack stack; 7 8 TreeNode *p = root; 9 10 while( NULL != p || !stack.empty())11 {12 while(NULL != p)13 {14 result.push_back(p->val);15 16 stack.push(p);17 p = p->left;18 }19 20 if(!stack.empty())21 {22 p= stack.top();23 stack.pop();24 25 p=p->right;26 }27 }28 29 return result;30 }31 32 };
1 class Solution { 2 public: 3 vector inorderTraversal(TreeNode *root) { 4 5 vector result; 6 stack stack; 7 8 TreeNode *p = root; 9 10 while( NULL != p || !stack.empty())11 {12 while(NULL != p)13 {14 stack.push(p);15 p = p->left;16 }17 18 if(!stack.empty())19 {20 p= stack.top();21 stack.pop();22 23 result.push_back(p->val);24 25 p=p->right;26 }27 }28 29 return result;30 }31 32 };
后续， 用bStack标记是否是第一次访问，如果是第一次访问，再次入栈，否则直接访问，记得将P = NULL；
1 class Solution { 2 public: 3 vector postorderTraversal(TreeNode *root) { 4 5 vector result; 6 stack stack; 7 std::stack bStack; 8 9 TreeNode *p = root;10 bool isFirst;11 12 while( NULL != p || !stack.empty())13 {14 while(NULL != p)15 {16 stack.push(p);17 bStack.push(false);18 p = p->left;19 }20 21 if(!stack.empty())22 {23 p= stack.top();24 stack.pop();25 26 isFirst = bStack.top();27 bStack.pop();28 29 if(isFirst == 0)30 {31 stack.push(p);32 bStack.push(true);33 p=p->right;34 }35 else36 {37 result.push_back(p->val);38 p = NULL;39 }40 41 }42 }43 44 return result;45 }46 47 };
另外一种前序迭代实现
1 class Solution { 2 public: 3 vector preorderTraversal(TreeNode *root) { 4 vector result; 5 const TreeNode *p; 6 stack s; 7 p = root; 8 if (p != nullptr) s.push(p); 9 while (!s.empty()) {10 p = s.top();11 s.pop();12 result.push_back(p->val);13 if (p->right != nullptr) s.push(p->right);14 if (p->left != nullptr) s.push(p->left);15 }16 return result;17 }18 };
Morris 遍历
morris分为3个步骤，建立link，访问最左节点，删除link，morris前序和中序遍历只要调整在那里visit节点即可，框架相同。。
可以参考：
Morris算法与递归和使用栈空间遍历的思想不同，它使用二叉树中的叶节点的right指针来保存后面将要访问的节点的信息，当这个right指针使用完成之后，再将它置为NULL，但是在访问过程中有些节点会访问两次，所以与递归的空间换时间的思路不同，Morris则是使用时间换空间的思想，先来看看Morris中序遍历二叉树的算法实现：
1 Morris 中序遍历
class Solution { public: void morris_inorder(TreeNode* T) { TreeNode *p, *temp; p = T; while(p) { if(p->left == NULL) { printf("%4d \n", p->val); p = p->right; } else { temp = p->left; // find the most right node of the p's left node while(temp->right != NULL && temp->right != p) { temp = temp->right; } if(temp->right == NULL) { temp->right = p; p = p->left; } else { printf("%4d \n", p->val); temp->right = NULL; p = p->right; } } } } }; 
同时, 以 下面的二叉树为例，走一遍流程：
4
/ \
2 7
/ \ / \
1 3 5 8
p指向4, temp指向2，然后while Loop，tmp指向3， 3->right = 4, p = p->left=2; 建立链接
p指向2， tmp指向1， 然后while Loop，tmp指向1, 1->right = 2, p = p->left = 1;建立链接
p指向1， 由于p->left == NULL，visit(1), p = p ->right = 2,
p指向2， tmp指向1， 然后while Loop，tmp指向1, visit(2), 1->right = NULL, p = p->right = 3;断开链接
p指向3， 由于p->left == NULL，visit(3), p = p ->right = 4,
p指向4， tmp指向2， 然后while Loop，tmp指向3, visit(4), 3->right = NULL, p = p->right = 7;断开链接
p指向7， tmp指向5， 然后while Loop，tmp指向5, 5->right = 7, p = p->left = 5;建立链接
p指向5， 由于p->left == NULL，visit(5), p = p ->right = 7,
p指向7， tmp指向5， 然后while Loop，tmp指向5, visit(7), 5->right = NULL, p = p->right = 8;断开链接
p指向8， 由于p->left == NULL，visit(3), p = p ->right = NULL,
退出循环
加上些打印信息，更好理解
class Solution { public: void morris_inorder(TreeNode* T) { TreeNode *p, *temp; p = T; while(p) { if(p->left == NULL) { printf("visit %4d \n", p->val); p = p->right; } else { temp = p->left; // find the most right node of the p's left node while(temp->right != NULL && temp->right != p) { temp = temp->right; } if(temp->right == NULL) { cout << "build link for " << temp->val <<"-->" << p->val << endl; temp->right = p; p = p->left; } else { printf("visit %4d \n", p->val); cout << "destory link for " << temp->val <<"-->" << p->val << endl; temp->right = NULL; p = p->right; } } } } };build link for 3-->4build link for 1-->2visit 1 visit 2 destory link for 1-->2visit 3 visit 4 destory link for 3-->4build link for 5-->7visit 5 visit 7 destory link for 5-->7visit 8
morris 前序遍历
void morris_preorder(TreeNode* T) { TreeNode *p, *temp; p = T; while(p) { if(p->left == NULL) { //visit the leftmost leaf node printf("visit %4d \n", p->val); p = p->right; } else { temp = p->left; // find the most right node of the p's left node while(temp->right != NULL && temp->right != p) { temp = temp->right; } if(temp->right == NULL) { //build the link printf("visit %4d \n", p->val); temp->right = p; p = p->left; } else { //remove the link temp->right = NULL; p = p->right; } } } }
3 morris 后序遍历
这里的reverse 和reverse单链表意思相同，另外之所以使用链表的reverse，而没有采用辅助stack后者vector是考虑要求空间复杂度O（1）的考虑
void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.{ if (from == to) return; TreeNode *x = from, *y = from->right, *z; while (true) { z = y->right; y->right = x; x = y; y = z; if (x == to) break; }}void printReverse(TreeNode* from, TreeNode *to) // print the reversed tree nodes 'from' -> 'to'.{ reverse(from, to); TreeNode *p = to; while (true) { printf("%d ", p->val); if (p == from) break; p = p->right; } reverse(to, from);}void postorderMorrisTraversal(TreeNode *root) { TreeNode dump(0); dump.left = root; TreeNode *cur = &dump, *prev = NULL; while (cur) { if (cur->left == NULL) { cur = cur->right; } else { prev = cur->left; while (prev->right != NULL && prev->right != cur) prev = prev->right; if (prev->right == NULL) { prev->right = cur; cur = cur->left; } else { printReverse(cur->left, prev); // call print prev->right = NULL; cur = cur->right; } } }}
还是以上述bst为例，走一遍code：
p指向dummy, temp指向4，然后while Loop，tmp指向8， 8->right = dummy, p = p->left=4; 建立链接
p指向4, temp指向2，然后while Loop，tmp指向3， 3->right = 4, p = p->left=2; 建立链接
p指向2， tmp指向1， 然后while Loop，tmp指向1, 1->right = 2, p = p->left = 1;建立链接
p指向1， 由于p->left == NULL， p = p ->right = 2,
p指向2， tmp指向1， 然后while Loop，tmp指向1, reversePrint(1,1), 1->right = NULL, p = p->right = 3;断开链接
p指向3， 由于p->left == NULL， p = p ->right = 4,
p指向4， tmp指向2， 然后while Loop，tmp指向3, reversePrint(2,3), 3->right = NULL, p = p->right = 7;断开链接
p指向7， tmp指向5， 然后while Loop，tmp指向5, 5->right = 7, p = p->left = 5;建立链接
p指向5， 由于p->left == NULL， p = p ->right = 7,
p指向7， tmp指向5， 然后while Loop，tmp指向5, reversePrint(5,5), 5->right = NULL, p = p->right = 8;断开链接
p指向8， 由于p->left == NULL，, p = p ->right = dummy,
p指向dummy， tmp指向4， 然后while Loop，tmp指向8, reversePrint(4,8), 8->right = NULL, p = p->right = null;断开链接
退出循环