打卡第十四天，今天学习二叉树。

今日任务

• 理论基础
• 递归遍历
• 迭代遍历
• 统一迭代

理论基础

二叉树是一种基础数据结构

二叉树的种类

• 满二叉树：只有度为0和为2的结点，而且度为0 的结点都在最后一层。
• 完全二叉树：结点按顺序从上到下，从左到右，中间不能缺。
• 二叉搜索树：有序的二叉树。
• 平衡二叉搜索树：有序的、而且左右子树高度差不超过1。

二叉树存储方式

• 链式存储
• 顺序存储

二叉树遍历方式

• 深度优先遍历
  • 前序遍历（中左右）
  • 中序遍历（左中右）
  • 后序遍历（左右中）
• 广度优先遍历

二叉树的定义

struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

定义跟链表相似，只是二叉树的指针指向左右孩子。

二叉树的递归遍历

递归思路

1. 确定递归函数的参数和返回值
   参数：二叉树的结点指针，保存二叉树结点元素的数组
   返回值：无返回值

   void traversal(TreeNode* cur, vector<int>& res)
   

2. 确定终止条件
   当结点为空的时候终止

   if(cur == NULL) return ;
   

3. 确定单层递归的逻辑
   中序遍历举例子：中序遍历是左中右，先递归找到最左边的结点，然后开始回溯，收集结点，在递归找最右边的结点

   traversal(cur->left, res);
   res.push_back(cur->val);
   traversal(cur->right, res);
   

给定一个二叉树的根节点 root ，返回 它的 前序 中序 后序 遍历 。

前序

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

中序

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> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

后序

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> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

二叉树的迭代遍历

前序

利用栈来完成迭代输出，前序遍历的顺序中左右，每一次先处理的是中间结点，那么先将根结点压入栈，然后再将右孩子压入栈，再是左孩子压入栈，顺序不要搞反了，因为栈的特点是先进后出，右子树比左子树慢访问。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> stack;vector<int> res;if(root) stack.push(root);while(!stack.empty()) {TreeNode* cur = stack.top();stack.pop();res.push_back(cur->val);if(cur->right) stack.push(cur->right);if(cur->left) stack.push(cur->left);}return res;}
};

中序

在迭代的过程中，其实我们有两个操作：

• 处理：将元素放进result数组中
• 访问：遍历节点

在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点，访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;                // 左} else {cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）st.pop();result.push_back(cur->val);     // 中cur = cur->right;               // 右}}return result;}
};

后序

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> st;if(root) st.push(root);while(!st.empty()) {TreeNode * cur = st.top();st.pop();res.push_back(cur->val);if(cur->left) st.push(cur->left);if(cur->right) st.push(cur->right);}reverse(res.begin(), res.end());return res;}
};

二叉树的统一迭代遍历

前序

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> res;if(root) st.push(root);while(!st.empty()) {TreeNode * cur = st.top();if(cur != nullptr) {st.pop();if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left); st.push(cur);st.push(nullptr);} else {st.pop();cur = st.top();st.pop();res.push_back(cur->val);}}return res;}
};

中序

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.top();    // 重新取出栈中元素st.pop();result.push_back(node->val); // 加入到结果集}}return result;}
};

后序

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> res;if(root) st.push(root);while(!st.empty()) {TreeNode * cur = st.top();if(cur != nullptr) {st.pop();st.push(cur);st.push(nullptr);if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left); } else {st.pop();cur = st.top();st.pop();res.push_back(cur->val);}}return res;}
};