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;
}
};
