【代码随想录】算法训练营 第十四天 第六章 二叉树 Part 1

递归遍历

递归法讲究的就是一个格式，在外边再定义一个用于递归求解的函数reverser，参数是递归的二叉树当前根节点和用于保存遍历得到的答案序列的vector容器；

函数中的格式就是，先写递归终止条件，也就是遍历的结点为空时，直接return，退出这轮遍历；再写遍历的操作，对于前序遍历，就是先保存当前结点的值，放入容器中，再递归调用reverser函数，分别先后遍历左子树和右子树。中序遍历和后序遍历就是调整三个操作的位置即可。

前序遍历

class Solution {
public:void traverser(TreeNode* cur, vector<int> &vec) {if (cur == NULL) return;vec.push_back(cur->val);traverser(cur->left, vec);traverser(cur->right, vec);}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traverser(root, result);return result;}
};

中序遍历

class Solution {
public:void reverser(TreeNode* cur, vector<int> &vec) {if (cur == NULL) return;reverser(cur->left, vec);vec.push_back(cur->val);reverser(cur->right, vec);}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;reverser(root, result);return result;}
};

后序遍历

class Solution {
public:void reverser(TreeNode* cur, vector<int> &vec) {if (cur == NULL) return;reverser(cur->left, vec);reverser(cur->right, vec);vec.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;reverser(root, result);return result;}
};

迭代遍历

迭代遍历就是不用递归的遍历，是用栈来实现的，今天时间不够了，只看了一遍随想录理解了一下思想，二刷回来补！