前言一、二叉树的前序遍历
问题描述解法一：递归解法二：迭代 二、二叉树的中序遍历
问题描述解法一：递归解法二：迭代 三、二叉树的后序遍历
题目描述解法一：递归方法二：迭代 总结
前言
递归三部曲：递归函数的参数和返回值、终止条件、单层递归的逻辑，144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历
一、二叉树的前序遍历 问题描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4:
示例 5：
解法一：递归输入：root = [1,null,2]
输出：[1,2]
前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
class Solution {
public:
void traversal(TreeNode* root,vector& res)
{
//终止条件
if(root==nullptr) return;
res.push_back(root->val);
traversal(root->left,res);
traversal(root->right,res);
}
vector preorderTraversal(TreeNode* root)
{
vector ans;
traversal(root,ans);
return ans;
}
};
解法二：迭代
我们使用栈来进行迭代，具体步骤为：
初始化栈，并将根节点入栈(满足循环条件)；
当栈不为空时：
弹出栈顶元素 node，并将值添加到结果中；
如果 node 的右子树非空，将右子树入栈；
如果 node 的左子树非空，将左子树入栈；
至于这里为什么由于栈是入栈时先将右子树入栈，是因为栈是“先进后出”的顺序，只有这样才会得到前序遍历结果为 “根->左->右”的顺序。
class Solution {
public:
vector preorderTraversal(TreeNode* root)
{
vector res;
stack st;
if(root!=nullptr)
{
st.push(root);
}
while(!st.empty())
{
TreeNode* cur=st.top();
st.pop();
res.push_back(cur->val);
if(cur->right!=nullptr)
{
st.push(cur->right);
}
if(cur->left!=nullptr)
{
st.push(cur->left);
}
}
return res;
}
};
二、二叉树的中序遍历
问题描述
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2] 输出：[1,2]解法一：递归
二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树。
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 ans;
inorder(root,ans);
return ans;
}
};
解法二：迭代
思路：
中序遍历“左中右”要先找到根结点的左结点，所以第一个被输出的结点会是整个二叉树的最左侧结点。对此，我们首先寻找其最左侧的子结点，同时用栈记录寻找经过的路径结点，这些是输出最左侧结点之后的返回路径。之后每次向上层父结点返回，弹栈输出上层父结点的同时判断此结点是否含有右子结点，如果存在则此右结点入栈并到达新的一轮循环，对此右结点也进行上述操作。
class Solution {
public:
vector inorderTraversal(TreeNode* root)
{
vector res;
stack st;
TreeNode* cur=root;
while(!st.empty()||cur!=nullptr)
{
//找到结点的最左侧结点,并且记录入栈
while(cur!=nullptr)
{
st.push(cur);
cur=cur->left;
}
// top定义是此刻的弹栈元素
TreeNode* top=st.top();
res.push_back(top->val);
st.pop();
// 处理过最左侧结点后，判断其是否存在右子树
if(top->right!=nullptr)
{
cur=top->right;
}
}
return res;
}
};
三、二叉树的后序遍历
题目描述
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]解法一：递归
二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树。
class Solution {
public:
void traversal(TreeNode* root,vector& res)
{
if(root==nullptr) return;
traversal(root->left,res);
traversal(root->right,res);
res.push_back(root->val);
}
vector postorderTraversal(TreeNode* root)
{
vector ans;
traversal(root,ans);
return ans;
}
};
方法二：迭代
后序遍历的迭代和中序遍历有异曲同工之妙
class Solution {
public:
vector postorderTraversal(TreeNode* root)
{
vector res;
stack st;
if(root != NULL)
st.push(root);
TreeNode* cur=root;
while(!st.empty())
{
TreeNode* top = st.top();
if(top->left != NULL && top->left != cur && top->right != cur)
{
st.push(top->left);
}
else if(top->right != NULL && top->right != cur)
st.push(top->right);
else
{
res.push_back(top->val);
st.pop();
cur = top;
}
}
return res;
}
};
总结
期待大家和我交流，留言或者私信，一起学习，一起进步！
