后序遍历145. Binary Tree Postorder Traversal
递归函数栈的方法很基础，写法也很简单，三种遍历方式之间只需要改变一行代码的位置即可
当树的深度过大时，函数栈可能会溢出，这时候需要我们使用数据结构中的栈，来模拟节点在栈中的压入和弹出
cur指针时刻指向需要处理的节点 如果当前节点不为空，则压入栈中，并改变cur指针指向其左节点 如果当前节点为空，也代表空节点的中序遍历自动完成，无需压栈，这时候需要弹出栈顶的节点，保存栈顶节点的值，并更改cur指向其右子树，以完成右子树的中序遍历
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> s; TreeNode* cur = root; while(cur || !s.empty()){ if(cur){ s.push(cur); cur = cur->left; } else { cur = s.top(); s.pop(); v.push_back(cur->val); cur = cur->right; } } return v; } };先序遍历与中序遍历代码相比只改变了保存节点的值的代码的位置，当先访问根的时候就记录节点，而不是等左子树遍历完，弹出根节点的时候再记录
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> s; TreeNode* cur = root; while(cur || !s.empty()){ if(cur){ v.push_back(cur->val); s.push(cur); cur = cur->left; } else { cur = s.top(); s.pop(); cur = cur->right; } } return v; } };因为后序遍历的压栈顺序是左-右-根，由于先遍历完左子树，然后遍历完右子树，然后才能处理当前节点，为了和之前的代码的结构保持一致，我们可以反向处理，也就是按根-右-左的顺序压栈， 结果反向输出即可
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> s; TreeNode* cur = root; while(cur || !s.empty()){ if(cur){ v.push_back(cur->val); s.push(cur); cur = cur->right; } else { cur = s.top(); s.pop(); cur = cur->left; } } reverse(v.begin(), v.end()); // 反向输出结果 return v; } };线索二叉树，O(n)时间，常数空间Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） 就是当前节点的中序遍历前驱节点，如果此前驱节点的右指针为空，则将此前驱节点的右指针指向当前节点 当寻找当前节点的中序遍历前驱节点时，发现能循环到自己，说明左子树已经遍历完，需要遍历右子树
同样先序遍历与中序遍历相比也只需要改变一行代码的位置
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { TreeNode* cur, *prev; vector<int> v; cur = root; prev = nullptr; while(cur){ if(cur->left == nullptr){ v.push_back(cur->val); cur = cur->right; } else { prev = cur->left; while(prev->right != nullptr && prev->right != cur) prev = prev->right; if(prev->right == nullptr){ v.push_back(cur->val); prev->right = cur; cur = cur->left; } else { prev->right = nullptr; cur = cur->right; } } } return v; } };后序遍历需要反向输出cur->left到cur的中序前驱结点之间的路径
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void reverse_traverse_reverse(TreeNode* cur, vector<int>& v){ TreeNode* prev = nullptr; while(cur){ auto right = cur->right; cur->right = prev; prev = cur; cur = right; } cur = prev; prev = nullptr; while(cur){ auto right = cur->right; cur->right = prev; v.push_back(cur->val); prev = cur; cur = right; } } vector<int> postorderTraversal(TreeNode* root) { TreeNode* cur, *prev; vector<int> v; cur = new TreeNode(-1); prev = nullptr; cur->left = root; while(cur){ if(cur->left == nullptr){ cur = cur->right; } else { prev = cur->left; while(prev->right != nullptr && prev->right != cur) prev = prev->right; if(prev->right == nullptr){ prev->right = cur; cur = cur->left; } else { prev->right = nullptr; reverse_traverse_reverse(cur->left, v); cur = cur->right; } } } return v; } };三种遍历方式中，后序遍历的处理比较麻烦，但是无论是使用递归栈，非递归栈还是Morris Traversal，代码的结构都是一样的，中序和前序甚至只有一行代码位置的差别 使用栈的版本中，最坏空间复杂度为O（n）链型，平均空间复杂度为O（lgn） Morris Traversal空间复杂度为O(1)
转载于:https://www.cnblogs.com/qbits/p/11163161.html
