作者：小卢
专栏：《Leetcode》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
144. 二叉树的前序遍历
题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例：
思路：
我们可以将二叉树一直向走到底，这样就会有一条道最左的路径，我们将其称为左子路，我们可以将二叉树分为左子路和左子路节点的右子树等等
我们利用一个栈来存储左子路，如果到底就出栈顶，然后遍历该栈顶的右子树以此循环
代码：
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*>st; vector<int>v; TreeNode*cur=root; while(cur||!st.empty()) { while(cur) { st.push(cur); v.push_back(cur->val); cur=cur->left; } TreeNode*top=st.top(); st.pop(); cur=top->right; } return v; } };
94. 二叉树的中序遍历
题目：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历
示例：
代码：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*>st; vector<int>v; TreeNode*cur=root; while(cur||!st.empty()) { while(cur) { st.push(cur); cur=cur->left; } TreeNode*top=st.top(); st.pop(); v.push_back(top->val); cur=top->right; } return v; } };
145. 二叉树的后序遍历
题目：
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例：
代码：
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*>st; vector<int>v; TreeNode*cur=root; TreeNode*prev=nullptr; while(cur||!st.empty()) { //左子路 while(cur) { st.push(cur); cur=cur->left; } //从栈里面取到左子路的节点 TreeNode*top=st.top(); //这里右不存在或者右子树已经遍历了，才可以 //prev记录上一个节点，如果prev是top的父亲，就说明右子树已经遍历了 if(top->right==nullptr||top->right==prev) { v.push_back(top->val); st.pop(); prev=top; } else { cur=top->right; } } return v; } };
