理论基础
二叉树的链式存储定义：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉树的定义和链表区别不大，只是节点里多了一个指针，分别指向左右孩子
遍历方式分类： 两种最基本的遍历方式，其内部又可进一步拓展：
-
广度优先遍历：一层一层的去遍历。
- 层次遍历
-
深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历：先行遍历根节点，中左右
- 中序遍历：中间遍历根节点，左中右
- 后序遍历：最后遍历根节点，左右中
二叉树的递归遍历
思路
二叉树的递归遍历是解决大部分问题的核心，其核心实现可以总结为三个要素：
-
确定递归函数的参数和返回值：首先要明确在递归过程中，需要处理哪些参数？每次递归的返回值是什么？以此来构造函数的 传入值 和 返回类型；
void traversal(TreeNode* cur, vector<int>& vec){ } -
确定终止条件：在实现递归函数时必须首先声明终止条件，才能避免溢出；
if (cur == NULL) return; -
确定单层递归的逻辑：最后再确定每一层需要处理的信息，实现重复调用的递归过程，这是递归函数实现的核心：
vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中 ，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
代码实现
前序遍历
class Solution {
public:
void pretravel(TreeNode* cur, vector<int>& result){
if(cur==NULL) return;
result.push_back(cur->val); // 中
pretravel(cur->left, result); // 左
pretravel(cur->right, result); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
pretravel(root, result);
return result;
}
};
中序遍历
class Solution {
public:
void postTravel(TreeNode* cur, vector<int>& tmp){
if(cur==NULL) return;
postTravel(cur->left, tmp);
postTravel(cur->right, tmp);
tmp.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
postTravel(root, result);
return result;
}
};
后序遍历
class Solution {
public:
void inorderTravel(TreeNode *cur, vector<int> &tmp){
if(cur==NULL) return;
inorderTravel(cur->left, tmp);
tmp.push_back(cur->val);
inorderTravel(cur->right, tmp);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorderTravel(root, result);
return result;
}
};
二叉树的迭代遍历
思路
递归正是借用了栈的特性实现一层层的返回，因此直接用栈也可以实现二叉树的前中后序遍历
前序遍历
对于前序遍历 “根-左-右” 的遍历顺序，先将根节点压入栈中并处理，随后将右孩子入栈，再将左孩子入栈（栈的先进后出）
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> result;
if (root == NULL) return result;
stk.push(root);
while(!stk.empty()){
TreeNode *node = stk.top(); // 中
stk.pop();
result.push_back(node->val);
if(node->right) stk.push(node->right); // 右(先进后出)
if(node->left) stk.push(node->left); // 左
}
return 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(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
};
二叉树的层序遍历
思路
- 层序遍历的实现非常简单，借助队列先进先出的特性，实现一层一层遍历的逻辑。
- 层序遍历的一个特殊点在于，结果需要一个二维容器来保存。因此无论是使用迭代还是递归，每新到一层要添加一个额外的逻辑，在结果容器下再创建一个小容器
代码实现
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;
// 首次到达该层，result大小=深度，随后新建个一维向量，result大小++
// 本层内就不会再触发该语句
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;
}
};
