二叉树理论基础
递归和迭代遍历相似处：入栈出栈均来自中节点，左右节点用来向下传递
二又树的递归遍历
视频讲解： 每次写递归都要靠直觉？ 这次带你学透二叉树的递归遍历！
前序遍历
代码
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;}
};后序遍历
代码
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右vec.push_back(cur->val); // 中
}中序遍历
代码
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左vec.push_back(cur->val); // 中traversal(cur->right, vec); // 右
}二叉树的迭代遍历
使用栈数据结构
视频讲解：
- 写出二叉树的非递归遍历很难么？（前序和后序）(opens new window)
- 写出二叉树的非递归遍历很难么？（中序）)
前序遍历
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();st.pop();if(node != nullptr) {result.push_back(node->val);st.push(node->right);st.push(node->left);}}return result;}
};后序遍历
前序遍历是“中左右”，在后续遍历中先变成“中右左”，得到数组结果再反转即可得到“左右中”的后序遍历
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();st.pop();if(node != nullptr){result.push_back(node->val);st.push(node->left);st.push(node->right);}}reverse(result.begin(),result.end());return result;}
};中序遍历
与前两种遍历不同之处：
- while循环中增加了cur != nullptr条件 （因为存在根节点只有右子树时当栈为空，循环还不能结束）
- 只有再遍历至空节点时才能有出栈操作
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;if(root != nullptr) st.push(root);while(cur != nullptr || !st.empty()){if(cur != nullptr){if(cur != root)st.push(cur);cur = cur->left;}else{TreeNode* node = st.top();st.pop();result.push_back(node->val);cur = node->right;}}return result;}
};二叉树的统一迭代法
核心思想：将每次要处理的节点（当前树下是中节点）放入栈后再向栈中加一个null值作为标记 ；
巧记：由于栈有后进先出特点，所有处理顺序应与遍历顺序相反
前序遍历
class Solution {
public:vector<int> preorderTraversal(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); // 右if (node->left) st.push(node->left); // 左st.push(node); // 中st.push(NULL);} else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};
后序遍历
class Solution {
public:vector<int> postorderTraversal(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();st.push(node); // 中st.push(NULL);if (node->right) st.push(node->right); // 右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> 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;}
};二叉树的层序遍历
视频讲解：讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历_哔哩哔哩_bilibili
递归代码：
引入一个深度变量 ，由深度决定当前层级
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;}
};
迭代代码：
关键：使用队列数据结构，并引入一个计数变量，用来决定每次出队列的元素个数 。每出队一个元素，就将其左右子孩入队列。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;queue<TreeNode*> q;if(root) q.push(root);while(!q.empty()){int sz = q.size();vector<int> v;while(sz--){TreeNode* node = q.front();q.pop();if(node != nullptr){v.push_back(node->val);if(node->left) q.push(node->left);if(node->right) q.push(node->right);}}result.push_back(v);}return result;}
};使用迭代代码解决如下10题易如反掌：
102.二叉树的层序遍历 --直接cv上述代码
107.二叉树的层次遍历II--将结果二维数组反转即可
199.二叉树的右视图--遍历结果二维数组只取每一维中最后一个元素
637.二叉树的层平均值--遍历结果二维数组并对每一维元素求平均值
429.N叉树的层序遍历--把之前循环中两个子节点换成多节点，并通过for循环方式入队列
515.在每个树行中找最大值--通过双重循环，对二维数组结果中每一维找最大值
116.填充每个节点的下一个右侧节点指针--每一层遍历时先用数组保存出队列节点，从第二个节点起让数组中最后一个元素next指针指向该节点
117.填充每个节点的下一个右侧节点指针II--同上，代码不变
104.二叉树的最大深度--每次while循环最后加上depth++
111.二叉树的最小深度--在上题基础上加一个判断条件：if(node->left == nullptr && node->right == nullptr)，当达到该条件，就跳出while循环
