前言
今日文案：
仰望天空时，什么都比你高，你会自卑；俯视大地时，什么都比你低，你会自负；只有放宽视野，把天空和大地尽收眼底，才能在苍穹泛土之间找到你真正的位置。无须自卑，不要自负，坚持自信。
递归真的很难用文字表述，我只能写一点我自己看得懂的内容了~
一、二叉树前序遍历
题目来源：
解题思路（迭代）：
所谓前序，就是中左右得遍历二叉树。
保留中值后，全部优先解析左边先，然后回头解析右边。
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ans; //创建一个存放答案的数组 stack<TreeNode*> st; //创建一个栈 if(root==0) return ans; st.push(root); //先存入头节点 while(!st.empty()) { TreeNode*node=st.top(); //弹出第一个元素来使用 st.pop(); ans.push_back(node->val); //保存值，此时的值是中值 if(node->right) //保存左右值，因为栈的特点，后进先出，先解析左边 st.push(node->right); if(node->left) st.push(node->left); } return ans; } };
解题思路（递归）
class Solution { public: void mysearch(TreeNode*cur,vector<int> &ans) { if(cur==0) return; ans.push_back(cur->val); //先插入中值 mysearch(cur->left,ans); //然后解析左 mysearch(cur->right,ans); //解析右 } vector<int> preorderTraversal(TreeNode* root) { vector<int> ans; mysearch(root,ans); return ans; } }
因为使用递归，三种遍历方式都差不多，只需要改变一下位置就行。
二、二叉树中序
解题思路：
先一股脑往左边差到最深，把左节点全部放进栈，然后解析栈，之后保留中值，然后放入右节点解析。
中、后序两者非常相像，只是顺序问题。
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != NULL || !st.empty()) { if (cur != NULL) { // 指针来访问节点，访问到最底层 st.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据） st.pop(); result.push_back(cur->val); // 中 cur = cur->right; // 右 } } return result; } };
总结
疲于奔命，二叉树的递归和迭代真的非常精妙一定要多画图理解。
