1. 遍历一棵树
前、中、后序遍历的路径实际是相同的，都是以如上路径去游历。
前、中、后序访问的结果不同，实际是访问节点的时机不同：
-
前序：一遇到节点就去访问
-
中序：访问完左树再去访问
-
后序：访问完右子树再去访问
如下是B节点的前、中、后序访问时机
2. 非递归遍历
2.1 理解
之前的递归遍历，将一棵树看成一个对称结构：左子树根右子树，借助递归函数，可以进入左右子树进行访问；
但如果想在当前函数内进行迭代访问，之前的左右子问题的方式就很难实现了。
这里我们不妨再看看这个遍历的路径图：
首先沿着最左侧向下走过A-B-D
然后向上，走D的右子树、B的右子树、A的右子树，走完A的右子树回来就代表遍历结束了
这里访问右子树就可以看成是一个子问题——访问以右节点为根的另一棵树,重新回到最一开始；
可以发现左侧节点第一次走到的顺序是从上至下：A-B-D，下一次遇到访问右子树的顺序又是D-B-A,恰好相反，因此可以用栈的结构，从左侧走的时候先把节点依次从上至下存起来，当遍历到底，遇到空的时候再取出栈顶的节点，通过这个节点去访问它的右树；
同时凭借着栈的结构，当进入右树，走到右树的节点，依然入此栈，当右树走完回来，右树所有入栈的节点也都已经取出，又只剩下了之前主干上的节点，还可继续主线逻辑，与递归方式的逻辑相似——不管递归出去的逻辑多复杂，完成了分支任务回来，我的主线任务还要正常进行。
2.2 实现
注：以下只提供了非递归游历整棵树的方法，前、中、后序访问节点的时机未写入，具体见后。
变量定义：
实现：
-
遍历最左侧节点，同时将他们依次入栈
-
开始取栈中元素
-
通过此节点访问它的右树
-
遍历结束的判断
- 栈中元素取完——栈空
- 同时当前的根节点对应一棵空树
- 仅栈空，对应上图中的根节点A访问完后，
但A节点还有右树，while判断时，cur是右树的根C
接下来访问C和它的左树、F和它的左树，当访问完Fcur指向F的右—null
此时栈空，cur == null，同时遍历也结束了。
-
子树为空的情况（返回主干问题）：
跳过当前树的遍历，从栈中取下一个节点
当前逻辑刚好可以实现
3. 前、中、后序遍历
前、中、后序遍历唯一的区别就是访问节点的时机不同
每个节点可以看成是有三次被经过：到达初遇，从左边回来再遇，遍历完右子树再遇，
这三次相遇恰好就对应前、中、后序的访问时机，
只需在迭代逻辑中找到这三次相遇的对应部分进行访问，即可完成前、中、后序遍历。
3.1 前序遍历
访问时机：第一次碰到，也就是左侧遍历要入栈的时候
此时访问，进行入栈即可。
vector<int> preorderTraversal(TreeNode* root)
{vector<int> v;//存储访问出元素stack<TreeNode*> st;//栈——临时储存节点TreeNode* cur = root;//用于游历整棵树的指针while (!st.empty() || cur){//遍历当前树的所有最左侧节点while (cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}//取出栈顶节点TreeNode* tmp = st.top();st.pop();//前序遍历右树cur = tmp->right;//更新root为栈顶节点的右树}return v;
}
3.2 中序遍历
访问时机：左侧节点访问已完成，节点出栈，马上要进入右树进行访问的时候
此时访问，进行入栈即可。
vector<int> inorderTraversal(TreeNode* root)
{vector<int> v;//存储访问出元素stack<TreeNode*> st;//栈——临时储存节点TreeNode* cur = root;//用于游历整棵树的指针while (!st.empty() || cur){//遍历当前树的所有最左侧节点while (cur){st.push(cur);cur = cur->left;}//取出栈顶节点TreeNode* tmp = st.top();st.pop();v.push_back(cur->val);//前序遍历右树cur = tmp->right;//更新root为栈顶节点的右树}return v;
}
3.3 后序遍历
在整棵右树访问完成，再次回到这个节点的时候进行访问
由于访问右树是一个多层的迭代遍历，无法在这个单次的代码上直接找到访问的位置
观察后，右子树进行后序遍历的最后一个访问的节点是右树的根节点，访问完这个节点的下一个节点就是当前要访问的节点
所以每次访问完一个节点，都将这个节点进行记录，节点要出栈都先判断栈顶节点对应的右节点是否为已记录节点
- 若是，则出栈并进行访问，同时更新用于记录的节点，此时右树无需访问，直接访问下一个栈顶元素
- 否则说明当前是②的位置，先不出栈，先访问右树，右树回来再出栈
**特殊情况：**当右树为空，这个节点也要访问
如访问B的右树完时候，prev是D，但此时B也得进行访问，所以右树为空也要加入出栈访问的判断条件
vector<int> postorderTraversal(TreeNode* root)
{vector<int> v;//存储访问出元素stack<TreeNode*> st;//栈——临时储存节点TreeNode* cur = root;//用于游历整棵树的指针TreeNode* prev = nullptr;while (!st.empty() || cur){//遍历当前树的所有最左侧节点while (cur){st.push(cur);cur = cur->left;}TreeNode* tmp = st.top();if (tmp->right == prev || tmp->right == nullptr){st.pop();v.push_back(tmp->val);prev = tmp;cur = nullptr;//下一次循环直接当空树访问下一个栈中节点}else{cur = tmp->right;//更新root为栈顶节点的右树}}return v;
}
