代码随想录算法训练营第六章 二叉树part01

** 递归遍历 **
leetcode链接：前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/682955973/ 后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/682955496/
题目描述：使用递归遍历实现二叉树的前中后序遍历。
核心思路：前序即是：中左右节点进行遍历 中序是：左中右节点遍历。 后序是左右中节点遍历。 递归法需注意：终止条件（cur == NULL）

点击查看代码

//前序遍历
```cpp
class Solution {
public:void trvalseval(TreeNode* cur,vector<int>& vec){if(cur == NULL)return;vec.push_back(cur->val);//中trvalseval(cur->left,vec);//左trvalseval(cur->right,vec);//右}vector<int> preorderTraversal(TreeNode* root) {vector<int> vec;trvalseval(root,vec);return vec;}
};
//后序遍历
```cpp
class Solution {
public:void traversal(TreeNode* cur,vector<int>& vec){if(cur == NULL)return;traversal(cur->left,vec);traversal(cur->right,vec);vec.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};
//中序遍历
```cpp
class Solution {
public:void traversal(TreeNode* cur,vector<int>& vec){if(cur == NULL)return;traversal(cur->left,vec);vec.push_back(cur->val);traversal(cur->right,vec);}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

**迭代遍历 ** leetcode链接：前序遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/682955973/ 后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/682955496/ 题目描述：使用迭代遍历实现二叉树的前中后序遍历。 核心思路：迭代法主要是手动创建栈，然后将节点压入栈。前序：先将root压入栈，然后出栈。接着先压入右节点，压入左节点，然后栈顶元素出栈（左节点），依次遍历。 中序：将root压入栈，然后一直将左子树的左节点遍历完，直到cur=NULL，当cur=NULL时，令cur=栈顶元素，然后cur=cur->right;（难以理解的情况下建议画图理解）依次遍历下去。 后序：先实现前序遍历，但是先遍历右子树，即中右左顺序遍历，然后将数组反转即是左右中。

点击查看代码

//前序
```cpp
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> vec;if(root == NULL)return vec;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();vec.push_back(cur->val);//此处需注意，一轮循环中，左节点和右节点都有遍历。if(cur->right != NULL){//cur = cur->right;st.push(cur->right);}if(cur->left != NULL){//cur = cur->left;st.push(cur->left);}}return vec;}
};
//中序
```cpp
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root == NULL)return result;TreeNode* cur = root;while(cur != NULL || !st.empty()){if(cur != NULL){st.push(cur);cur = cur->left;}else{cur = st.top();result.push_back(cur->val);cur = cur->right;st.pop();}}return result;}
};
//后序
```cpp
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if(root == NULL)return result;stack<TreeNode*> st;st.push(root);//不需要cur!=NULL，因为cur永远不会是NULL，除非root为空，未判断while(!st.empty()){TreeNode* cur = st.top();result.push_back(cur->val);st.pop();if(cur->left != NULL){st.push(cur->left);}if(cur->right != NULL){st.push(cur->right);}}reverse(result.begin(),result.end());return result;}
};