今日刷题重点–二叉树的递归+迭代遍历
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3] 示例 2：
输入：root = []
输出：[] 示例 3：
输入：root = [1]
输出：[1] 其他相似问题
145. 二叉树的后序遍历
94. 二叉树的中序遍历
1.递归
//递归的做法
class Solution {
public:
void traverse(TreeNode* cur,vector<int>& vec) { //递归遍历
if(cur) { //先序遍历
vec.push_back(cur->val);
traverse(cur->left,vec);
traverse(cur->right,vec);
}
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
traverse(root,vec);
return vec;
};
}; 2.迭代
先序遍历
因为递归底层使用的是栈,所以我们可以直接使用栈来解决问题.
先序是按照中左右的顺序,每次先处理的是中间节点,那么我们处理时要先将右孩子加入栈,再加入左孩子.
为什么要按照这样的入栈顺序呢?因为先入栈的后遍历,后入栈的先遍历.
如图所示:
参考代码:
//先序遍历 中左右
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> tab;
vector<int> res;
if(root==NULL) {
return res;
}
tab.push(root);
while(!tab.empty()) {
TreeNode* cur = tab.top();
tab.pop();
res.push_back(cur->val);
if(cur->right) {
tab.push(cur->right);
}
if(cur->left) {
tab.push(cur->left);
}
}
return res;
}; 后序遍历
由于先序是:中左右,后序是:左右中,所以我们可以调整下先序代码的顺序便可完成操作.
//后序遍历: 左右中 可以直接从前序的代码上修改一点即可.
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> tab;
vector<int> res;
if(root==NULL) {
return res;
}
tab.push(root);
while(!tab.empty()) {
TreeNode* cur = tab.top();
tab.pop();
res.push_back(cur->val);
if(cur->left) {
tab.push(cur->left);
}
if(cur->right) {
tab.push(cur->right);
}
}
reverse(res.begin(),res.end());
return res;
} 中序遍历
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
//中序遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> tab;
TreeNode* cur = root;
if(root==NULL){
return res;
}
while(cur!=NULL || !tab.empty()){//直到栈为空并且当前节点 也为空,则结束.
if(cur!=NULL){
tab.push(cur);//如果当前节点不为空,则将当前节点先压入栈,继续进行访问.
cur = cur->left;//当把当前结点的左子树访问完了,在处理当期节点. =>左
}else{//结点的左子树为空,则开始弹出该节点处理完毕后,开始访问处理右子树.
cur = tab.top();//
tab.pop();
res.push_back(cur->val);//中
cur = cur->right; //右
}
}
return res;
}