标签：right TreeNode val 前中 层序 nullptr int 遍历 left
- 前言
- 非递归算法中,前中后序遍历需要借助栈,层序遍历需要借助队列
- 前中后序遍历的递归算法中,语法大致相同,只是执行顺序不同,注意
前序遍历
方法一:递归算法
/**
* 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>ans;
vector<int> preorderTraversal(TreeNode* root) {
preOrder(root);
return ans;
}
void preOrder(TreeNode* t){
if(!t)
return;
ans.push_back(t->val);
preorderTraversal(t->left);
preorderTraversal(t->right);
}
};
方法二:非递归算法
/**
* 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) {
TreeNode*p=root;
stack<TreeNode*>st;
vector<int>ans;
while(p!=NULL || !st.empty()){
while(p!=NULL){
ans.push_back(p->val);
st.push(p);
p=p->left;
}
p=st.top()->right;
st.pop();
}
return ans;
}
};
中序遍历
方法一:递归算法
/**
* 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>ans;
void inOrder(TreeNode*root){
if(root==NULL)
return;
inOrder(root->left);
ans.push_back(root->val);
inOrder(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
inOrder(root);
return ans;
}
};
方法二:非递归算法
/**
* 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>ans;
stack<TreeNode*>st;
TreeNode*p=root;
while(p!=NULL || !st.empty()){
while(p!=NULL){
st.push(p);
p=p->left;
}
ans.push_back(st.top()->val);
p=st.top()->right;
st.pop();
}
return ans;
}
};
后序遍历
方法一:递归算法
/**
* 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>ans;
vector<int> postorderTraversal(TreeNode* root) {
postOrder(root);
return ans;
}
void postOrder(TreeNode*p){
if(!p)
return;
postOrder(p->left);
postOrder(p->right);
ans.push_back(p->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) {
stack<TreeNode*>st;
TreeNode*p=root;
TreeNode*pre=NULL;//标记刚刚被访问过的元素
vector<int>ans;
while(p!=NULL || !st.empty()){
while(p!=NULL){
st.push(p);
p=p->left;
}
//栈顶元素右孩子为空或者已经访问过栈顶元素的右孩子,则访问栈顶元素
if(st.top()->right==NULL || pre==st.top()->right){
ans.push_back(st.top()->val);
pre=st.top();
st.pop();
}
//当栈顶元素有右孩子企鹅没有被访问过,就访问栈顶元素的右孩子
else
p=st.top()->right;
}
return ans;
}
};
层序遍历
标签：right,
TreeNode,
val,
前中,
层序,
nullptr,
int,
遍历,
left
From： https://www.cnblogs.com/cxyupup/p/17360465.html