Leetcode数据结构入门第十天（树的遍历）
144、二叉树的前序遍历
题目描述样例思路一参考代码思路二参考代码 94、二叉树的中序遍历
题目描述样例思路一参考代码思路二参考代码 145、二叉树的后序遍历
题目描述样例思路一参考代码思路二参考代码 144、二叉树的前序遍历 题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
样例
输入：root = [1,null,2,3]输出：[1,2,3]输入：root = []输出：[]
思路一
递归法：
先序遍历：访问根节点——左子树——右子树遍历，从根节点root开始，然后访问他的左子树和右子树，访问左子树或者右子树时，也是按照这样顺序遍历，不断递归，直到根节点为空，递归结束。
参考代码
class Solution {public: //递归法:先序遍历 //用于递归的函数 void preorder(TreeNode* root,vector &res) { //根节点为空，返回，（递归终点） if(root==NULL) return; //先访问根 res.push_back(root->val); //递归遍历：左子树 preorder(root->left,res); //递归遍历：右子树 preorder(root->right,res); } vector preorderTraversal(TreeNode* root) { //遍历结果 vector res; //调用递归函数：从根节点开始 preorder(root,res); //返回遍历结果 return res; }};
思路二
迭代法：思路一的递归方法实际上就是隐式维护了一个栈，所以我们可以显式地实现，即迭代法。先序遍历就是根–左-右，所以我们遍历的时候，首先把根节点值压入res容器中，栈压入根节点，内层不断循环，一直往左下走，直到走投无路（即根节点为空），结束内层循环，通过弹出栈顶元素，把栈顶元素的右节点赋给根节点，重新继续内层循环，向左下遍历。
参考视频讲解
参考代码
class Solution {public: //迭代法:先序遍历 vector preorderTraversal(TreeNode* root) { //遍历结果 vector res; //栈 stack st; //从根节点开始，栈不为空 while(root!=NULL||!st.empty()) { //遍历根 while(root!=NULL) { //根节点值压入结果 res.push_back(root->val); //把根节点压入栈 st.push(root); //根节点：向左下走 root=root->left; } //左下走，走不下去，弹出栈 //获得栈顶元素 root=st.top(); //弹出栈 st.pop(); //根节点=栈顶元素的右节点 root=root->right; } //返回遍历结果 return res; }};
94、二叉树的中序遍历 题目描述
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
样例
输入：root = [1,null,2,3]输出：[1,3,2]输入：root = []输出：[]
思路一
递归法：基本和先序遍历的思路一致，不再赘述
参考代码
class Solution {public: //递归法:中序遍历 //用于递归的函数 void inorder(TreeNode* root,vector &res) { //根节点为空，返回，（递归终点） if(root==NULL) return; //递归遍历：左子树 inorder(root->left,res); //遍历根 res.push_back(root->val); //递归遍历：右子树 inorder(root->right,res); } vector inorderTraversal(TreeNode* root) { //遍历结果 vector res; //调用递归函数：从根节点开始 inorder(root,res); //返回遍历结果 return res; }};
思路二
迭代法：思路一的递归方法实际上就是隐式维护了一个栈，所以我们可以显式地实现，即迭代法。中序遍历就是左-根-右，所以我们遍历的时候，与前序遍历不同的就是压入节点的值顺序不同，所以我们首先把栈压入根节点，内层不断循环，一直往左下走，直到走投无路（即根节点为空），结束内层循环，通过弹出栈顶元素，在这里压入的是栈顶元素节点值到res中，然后把栈顶元素的右节点赋给根节点，重新继续内层循环，向左下遍历。
参考代码
class Solution {public: //迭代法：中序遍历：左根右 vector inorderTraversal(TreeNode* root) { //遍历结果 vector res; stack st; //从根节点开始：栈非空或根非空 while(root!=NULL||!st.empty()) { //根节点非空:往左下走 while(root!=NULL) { //这里不用压入根节点值 //压入根栈 st.push(root); root=root->left; } //走投无路： 压入栈顶的元素节点值，弹出栈 //获得栈顶 root=st.top(); //压入栈顶元素值 res.push_back(root->val); //出栈 st.pop(); //根节点=栈顶右孩子 root=root->right; } //返回遍历结果 return res; }};
145、二叉树的后序遍历 题目描述
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
样例
输入：root = [1,null,2,3]输出：[3,2,1]输入：root = []输出：[]
思路一
递归法：
基本和先序遍历的思路一致，不再赘述
参考代码
class Solution {public: //递归法:后序遍历 //用于递归的函数 void postorder(TreeNode* root,vector &res) { //根节点为空，返回，（递归终点） if(root==NULL) return; //递归遍历：左子树 postorder(root->left,res); //递归遍历：右子树 postorder(root->right,res); //最后遍历根 res.push_back(root->val); } vector postorderTraversal(TreeNode* root) { //遍历结果 vector res; //调用递归函数：从根节点开始 postorder(root,res); //返回遍历结果 return res; }};
思路二
迭代法：思路一的递归方法实际上就是隐式维护了一个栈，所以我们可以显式地实现，即迭代法。先序遍历就是根–左-右，而后序遍历是“左-右-根”，所以我们可以先按照根-右-左来实现，最后来反转res即可。而根-右-左，类似于先序遍历，只是左右不同而已。
遍历的时候，首先把根节点值压入res容器中，栈压入根节点，内层不断循环，一直往右下走，直到走投无路（即根节点为空），结束内层循环，通过弹出栈顶元素，把栈顶元素的左节点赋给根节点，重新继续内层循环，向右下遍历。循环全部结束后，反转res即可。
参考代码
class Solution {public: //迭代法：后序遍历:左右根-> 先变成根右左，再反转即可 vector postorderTraversal(TreeNode* root) { //遍历结果 vector res; //栈 stack st; //从根节点开始，栈不为空 while(root!=NULL||!st.empty()) { //根节点不为空 while(root!=NULL) { //根节点值压入结果 res.push_back(root->val); //把根节点压入栈 st.push(root); //向右下走 root=root->right; } //右下走投无路，弹出栈:根节点=栈顶的左孩子 //获得栈顶 root=st.top(); //出栈 st.pop(); //根节点=栈顶的左孩子 root=root->left; } //反转： reverse(res.begin(),res.end()); //返回遍历结果 return res; }};