day14 二叉树的遍历递归遍历迭代遍历统一遍历-拓冰建站

题目1：递归遍历

题目链接1：144 二叉树的前序遍历

题意

根据二叉树的根节点root，返回它的前序遍历

递归法

前序遍历：中左右

递归三部曲

1) 确定递归函数的参数和返回值

2）确定终止条件

3）确定单层递归逻辑

伪代码

代码

/*** 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>& result){//终止条件if(cur==NULL){return;}//单层递归逻辑//前序:中左右result.push_back(cur->val);//中traversal(cur->left,result);//左traversal(cur->right,result);//右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

迭代法

代码

/*** 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> result;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();st.pop();if(node!=NULL){result.push_back(node->val);}else{continue;}if(node->right){st.push(node->right);}if(node->left){st.push(node->left);}}return result;}
};

题目2：145 二叉树的后序遍历

题目链接2：145 二叉树的后序遍历

题意

根据二叉树的根节点root，返回它的后序遍历

递归法

后序遍历：左右中

递归三部曲：

1) 确定递归函数的参数和返回值

2）确定终止条件

3）确定单层递归逻辑

伪代码

代码

/*** 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>& result){//终止条件if(cur==NULL){return;}//单层递归逻辑traversal(cur->left,result);//左traversal(cur->right,result);//右result.push_back(cur->val);//中}vector<int> postorderTraversal(TreeNode* root){vector<int> result;traversal(root,result);return result;}
};

迭代法

代码

/*** 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> result;stack<TreeNode*> st;st.push(root);//终止条件while(!st.empty()){TreeNode* node = st.top();st.pop();if(node!=NULL){result.push_back(node->val);}else{continue;}if(node->left){st.push(node->left);}if(node->right){st.push(node->right);}}reverse(result.begin(),result.end());return result;}
};

题目3：94 二叉树的中序遍历

题目链接3：94 二叉树的中序遍历

题意

根据二叉树的根节点root，返回它的后序遍历

递归法

中序遍历：左中右

递归三部曲：

1) 确定递归函数的参数和返回值

2）确定终止条件

3）确定单层递归逻辑

伪代码

代码

/*** 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>& result){//终止条件if(cur==NULL){return;}//中序遍历，左中右traversal(cur->left,result);//左result.push_back(cur->val);//中traversal(cur->right,result);//右}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

迭代法

如果按照前序遍历和后序遍历的迭代法来，那么访问的元素和要处理的元素顺序不一致

所以，需要一个指针cur指针遍历节点，栈处理遍历过的节点

代码

/*** 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> result;stack<TreeNode*> st;TreeNode* cur = root;while(!st.empty() || cur!=NULL){//向左一直遍历if(cur!=NULL){st.push(cur);cur = cur->left;//左}//向左遍历遇到空节点else{//加入当前节点，相当于中节点，并更新当前指针cur = st.top();st.pop();result.push_back(cur->val);//中//遍历当前节点的右孩子cur = cur->right;//也是一颗二叉树，继续同样的操作(一直向左，当前节点，右孩子)}}return result;}
};