理论基础

种类

满二叉树：节点总数为 $2^k-1$，$k$为层数。
完全二叉树：最底层节点连续。堆是完全二叉树。
二叉搜索树：左子树节点都小于中间节点，右子树都大于中间节点。时间复杂度为 $O(\log n)$。该树对于结构没有要求，只对节点大小有要求。
平衡二叉搜索树（红黑树）：平衡：左子树和右子树高度的绝对值之差不能超过1。map set multimap multiset底层都是平衡二叉搜索树。

存储方式

链式存储：树的形式
线式存储：节点依次取值，置于数组中。对于索引为 $i$ 的元素，其左子节点对应的索引为 $2\times i+1$，其右子节点对应的索引为 $2\times i+2$。该二叉树为完全二叉树，索引是从0开始的。

遍历方式

深度优先搜索(Depth First Search, DFS)，通常用递归来实现。前序、中序和后序遍历都属于深度优先搜索。编程语言就是用栈的形式来实现递归。也可以用迭代法（非递归）实现深度优先搜索。 任何递归的方法，都可以改成迭代法。
前序遍历：中左右。中序遍历：左中右。后序遍历：左右中。前、中和后指的是中间节点的顺序。

广度优先搜索(Breadth First Search, BFS)，层层遍历。层序遍历属于广度优先搜索。迭代法，使用队列对二叉树一层一层搜索。当然也可以用递归。

定义

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) {}
};

---

递归遍历

递归三部曲：

• 确定递归函数的参数和返回值，可以后续修改
• 确定终止条件
• 确定单层递归的逻辑

144. 二叉树的前序遍历

题目链接:144. 二叉树的前序遍历

• void traversal(TreeNode* cur, vector<int>& vec);
• 深度优先搜索，一直往下搜，直到遇到空节点 if (cur == nullptr) return;
• 中左右。res.push_back(cur->val); traversal(cur->left, vec); traversal(cur->right, vec);

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

145.二叉树的后序遍历

题目链接:145.二叉树的后序遍历

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

94.二叉树的中序遍历

题目链接:94.二叉树的中序遍历

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

---

迭代遍历

迭代就是层层遍历。用栈模拟，栈是先进后出。

144. 二叉树的前序遍历

题目链接:144. 二叉树的前序遍历
访问节点和处理节点顺序一样。

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

因为是模仿栈的操作，所以右先入栈，左再入栈。左会先出栈，加入到数组中，右再出栈。达到中左右的顺序。

145.二叉树的后序遍历

题目链接:145.二叉树的后序遍历
前序遍历是中左右，改成中右左，通过调换循环中语句。最后得到的数组再反转，变为左右中。

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> res;if (!root) return {};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;}
};

94.二叉树的中序遍历

题目链接:94.二叉树的中序遍历
访问节点和处理节点的顺序不一样。访问一定是从根节点开始访问的。用栈记录遍历过的顺序。
对每个节点都查找一下左右子节点。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> st;TreeNode* cur = root;//遍历树while (cur != nullptr || !st.empty()) {if (cur != nullptr) {//最左节点st.push(cur);cur = cur->left;//左} else {cur = st.top();//记录节点，方便查找右子节点st.pop();res.push_back(cur->val);//中cur = cur->right;//右}}return res;}
};

---

统一迭代

将访问节点和处理节点的方法统一，可以统一前、中、后序遍历的代码。
处理节点放入栈之后，接着放入一个空指针作为标记。
因为处理出栈节点为空节点时，将下一个节点出栈，且赋给数组。所以需要将中间节点入栈后，再入栈空节点。

94.二叉树的中序遍历

题目链接:94.二叉树的中序遍历

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> st;if (root) st.push(root);//为了统一循环，需要让stack有元素while (!st.empty()) {TreeNode* cur = st.top();st.pop();if (cur) {if(cur->right) st.push(cur->right);//右//中st.push(cur);st.push(nullptr);//标记用的，访问为空的分支if(cur->left) st.push(cur->left);//左} else {//只有空节点才会弹出res.push_back(st.top()->val);//获取下一个节点，并赋给resst.pop();//元素用完了，记得弹出}}return res;}
};

else处理的是出栈，if处理的入栈。统一了入栈，出栈的顺序。

144. 二叉树的前序遍历

题目链接:144. 二叉树的前序遍历

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

145.二叉树的后序遍历

题目链接:145.二叉树的后序遍历

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();if (cur) {//中st.push(cur);st.push(nullptr);if (cur->right) st.push(cur->right);//右if (cur->left) st.push(cur->left);//左} else {res.push_back(st.top()->val);st.pop();}}return res;}
};