144.二叉树的前序遍历
思路:有递归法和使用栈来模拟递归的迭代法。
代码:
1.递归
/**
* 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:
void Traversal(TreeNode* cur,vector<int>& res){
if(cur==NULL)
return;
res.push_back(cur->val);
Traversal(cur->left,res);
Traversal(cur->right,res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root,res);
return res;
}
};
2.迭代
/**
* 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) {
stack<TreeNode*> st;
vector<int> res;
if(root==NULL)
return res;
TreeNode* cur=root;
st.push(cur);
while(!st.empty()){
cur=st.top();
res.push_back(cur->val);
st.pop();
if(cur->right) st.push(cur->right);
if(cur->left) st.push(cur->left);
}
return res;
}
};
94、二叉树的中序遍历
思路:递归,迭代
代码:
1.递归
/**
* 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:
void Traversal(TreeNode* cur,vector<int>& res){
if(cur==NULL)
return;
Traversal(cur->left,res);
res.push_back(cur->val);
Traversal(cur->right,res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root,res);
return res;
}
};
2.迭代
/**
* 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) {
stack<TreeNode*> st;
vector<int> res;
if(root==NULL) return res;
TreeNode* cur=root;
st.push(cur);
cur=cur->left;
while(cur!=NULL||!st.empty()){
if(cur!=NULL){
st.push(cur);
cur=cur->left;
}
else{
cur=st.top();
st.pop();
res.push_back(cur->val);
cur=cur->right;
}
}
return res;
}
};
145、二叉树的后序遍历
思路:递归,迭代
代码:
1.递归
/**
* 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:
void Traversal(TreeNode* cur,vector<int>& res){
if(cur==NULL)
return;
Traversal(cur->left,res);
Traversal(cur->right,res);
res.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
Traversal(root,res);
return res;
}
};
2.迭代
/**
* 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) {
stack<TreeNode*> st;
vector<int> res;
if(root==NULL)
return res;
st.push(root);
TreeNode* node=root;
while(!st.empty()){
node=st.top();
st.pop();
res.push_back(node->val);
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
reverse(res.begin(),res.end());
return res;
}
};
102.二叉树的层序遍历
思路:队列
代码:
/**
* 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) {
queue<TreeNode*> que;
vector<vector<int>> res;
if (root == NULL) return res;
que.push(root);
while (!que.empty()) {
int size = que.size();
vector<int> a;
while (size--) {
TreeNode* node = que.front();
que.pop();
a.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
res.push_back(a);
}
return res;
}
};
标签:遍历,TreeNode,cur,val,res,right,二叉树,第十三天,left
From: https://blog.csdn.net/dtgfhfd/article/details/140451168