文章目录
- 二叉树理论基础
- 递归遍历
-
- 迭代遍历
-
- 统一遍历
-
- 层序遍历
-
二叉树理论基础
递归遍历
- 题目链接：
- 144. 二叉树的前序遍历 - 力扣（LeetCode）
- 145. 二叉树的后序遍历 - 力扣（LeetCode）
- 94. 二叉树的中序遍历 - 力扣（LeetCode）
- 讲解链接：代码随想录
- 状态：一遍AC。
思路与重点
- 递归算法的三要素：
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
- 前序遍历的递归版本：
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:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top(); st.pop();result.push_back(node->val);if (node->right) st.push(node->right); if (node->left) st.push(node->left); }return result;}
};
- 后序遍历：先序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后再反转result数组，输出的结果顺序就是左右中了。
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();result.push_back(node->val);if (node->left) st.push(node->left); if (node->right) st.push(node->right); }reverse(result.begin(), result.end()); return 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(); st.pop();result.push_back(cur->val); cur = cur->right; }}return result;}
};
统一遍历
思路与重点
- 我们以中序遍历为例，使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
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;}
};
层序遍历
- 题目链接：
- 102. 二叉树的层序遍历 - 力扣（LeetCode）
- 107. 二叉树的层序遍历 II - 力扣（LeetCode）
- 199. 二叉树的右视图 - 力扣（LeetCode）
- 637. 二叉树的层平均值 - 力扣（LeetCode）
- 429. N 叉树的层序遍历 - 力扣（LeetCode）
- 515. 在每个树行中找最大值 - 力扣（LeetCode）
- 116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）
- 117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）
- 104. 二叉树的最大深度 - 力扣（LeetCode）
- 111. 二叉树的最小深度 - 力扣（LeetCode）
- 讲解链接：代码随想录
- 状态：一遍AC。
思路与重点
- 队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};# 递归法
class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};
- int maxValue = INT_MIN; 也就是**-2^31**
