算法刷题-二叉树
144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路
前序遍历：中左右
使用栈的时候要注意：先放右儿子，再放左儿子，再放中间，这样可以保证出栈的时候：中左右
放自己的时候，需要放一个空指针作为标记
代码
递归版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root,res);
return res;
}
void dfs(TreeNode *root ,vector<int> &res){
if(root==nullptr) return;
res.push_back(root->val);
dfs(root->left,res),dfs(root->right,res);
}
};
栈版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if(root!=nullptr) st.push(root);
while(!st.empty()){
auto t=st.top();
st.pop();
if(t!=nullptr){
//中左右
if(t->right) st.push(t->right);
if(t->left) st.push(t->left);
st.push(t),st.push(nullptr);
}else{
t=st.top();
st.pop();
res.push_back(t->val);
}
}
return res;
}
};
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
思路
后序遍历：左右中
使用栈遍历的时候，先放自己，在右儿子，在左儿子。这样可以保证出栈的时候顺序为：左右中
代码
递归版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root,res);
return res;
}
void dfs(TreeNode *root,vector<int> &res){
if(root==nullptr) return;
dfs(root->left,res),dfs(root->right,res);
res.push_back(root->val);
}
};
栈版本：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if(root!=nullptr) st.push(root);
while(!st.empty()){
auto t=st.top();
st.pop();
if(t==nullptr){
t=st.top();
st.pop();
res.push_back(t->val);
}else{
//左右中
st.push(t),st.push(nullptr);
if(t->right)st.push(t->right);
if(t->left)st.push(t->left);
}
}
return res;
}
};
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
思路
中序遍历：左中右
在使用栈遍历的时候，先让右儿子，再放左儿子，再放中间，这样可以保证出来的时候顺序为：左中右
放自己的时候，再放一个空指针作为标记，下次遍历到空指针的时候，下一个就是自己
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root,res);
return res;
}
void dfs(TreeNode *root,vector<int> &res){
if(root==nullptr) return;
dfs(root->left,res);
res.push_back(root->val);
dfs(root->right,res);
}
};
栈版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if(root!=nullptr) st.push(root);
while(!st.empty()){
auto t=st.top();
if(t!=nullptr){
st.pop();
if(t->right) st.push(t->right);
st.push(t);
st.push(nullptr);
if(t->left) st.push(t->left);
}else{
st.pop();
t=st.top();
st.pop();
res.push_back(t->val);
}
}
return res;
}
};
102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
思路
使用队列进行广度优先搜索，每次需要push_back的vector的大小应该根据上一次还剩余的队列的长度进行计算。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if(root!=nullptr) q.push(root);
while(q.size()){
int sz=q.size();
vector<int> cur;
while(sz--){
auto t=q.front();
q.pop();
cur.push_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
res.push_back(cur);
}
return res;
}
};
107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
思路
在上一题的基础上，只需要将从上往下遍历的结果reverse一下即可。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> res;
if(root!=nullptr) q.push(root);
while(q.size()){
int sz=q.size();
vector<int> cur;
while(sz--){
auto t=q.front();
q.pop();
cur.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
res.push_back(cur);
}
reverse(res.begin(),res.end());
return res;
}
};
