算法训练营第十三天：二叉树基础

算法训练营第十三天|

• 二叉树理论基础
• 二叉树的递归遍历
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现（前序遍历）中，左，右
    • c++实现（中序遍历）左，中，右
    • c++实现（后序遍历）左，右，中
• 二叉树的迭代遍历
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现（前序遍历）中，左，右
    • c++实现（中序遍历）左，中，右
    • c++实现（后序遍历）左，右，中
• 二叉树的统一迭代法
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现 （前序遍历）使用null表示使用
    • c++实现 (中序遍历）使用null表示使用
    • c++实现 (后序遍历）使用null表示使用
    • c++实现 (中序遍历）使用 pair 携带一个bool来确定元素状态
• 二叉树层序遍历
• • 卡哥文字以及视频讲解链接
  • • 重点
    • c++实现
  • 一个重点
• 坚持就是胜利

二叉树理论基础

• 二叉树类型有：满二叉树、完全二叉树、二叉搜索树和平衡二叉搜索树。
• 存储方式有：链式存储（指针）和顺序存储（数组）。
• 遍历方式有：
• 深度优先：前中后序遍历（递归，迭代）
• 广度优先：层序遍历（迭代）
• 二叉树结点的定义

* Definition for a binary tree node.
* 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) {}
* };

二叉树的递归遍历

卡哥文字以及视频讲解链接

重点

• 二叉树的学习引入了递归的大量使用
• 递归三要素：
• 确定递归函数的参数和返回值
• 确定终止条件
• 确定单层递归的逻辑
• 递归开销大，内存占用久

c++实现（前序遍历）中，左，右

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
// if(root == nullptr) return {};三处注释搭配使用，起到递归函数中的终止条件作用
vector<int> result;
travalTree(root, result);
return result;
}
void travalTree(TreeNode* root, vector<int>& result){//这个引用很重要
if(root == nullptr) return;//终止条件
result.push_back(root -> val);//中
/*if(root -> left)*/ travalTree(root -> left, result);//左孩子
/*if(root -> right)*/ travalTree(root -> right, result);//右孩子
return;
}
};

c++实现（中序遍历）左，中，右

class Solution {
public:
std::vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> result;
traverse(root, result);
return result;
}
private:
void traverse(TreeNode* node, std::vector<int>& res) {
if (node == nullptr) return;//递归终止条件
traverse(node->left, res);//左
res.push_back(node->val);//中
traverse(node->right, res);//右
}
};

c++实现（后序遍历）左，右，中

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
travalTree(root, result);
return result;
}
void travalTree(TreeNode* root, vector<int>& result){
if(root == nullptr) return;
travalTree(root -> left, result);
travalTree(root -> right, result);
result.push_back(root -> val);
}
};

二叉树的迭代遍历

卡哥文字以及视频讲解链接

重点

• 手动实现一遍，按照实现步骤转换成代码，就理解了
• 就是一个栈，放进放出。
• 只用栈，所有的循环判断依靠的是栈本身。弹出顺序和使用顺序一致。
• 中序遍历使用一个栈无法实现，就是因为栈顶节点和要使用节点不一致。循环判断条件依靠的是帮助指定的指针和栈本身。

c++实现（前序遍历）中，左，右

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(root == nullptr) return result;//检查非空，防止越界
st.push(root);//和while条件搭配
while(!st.empty()){
TreeNode* temp = st.top();
st.pop();
result.push_back(temp -> val);
//栈的特点，先进后出，所以要先使用就要后放。先放右，再放左
if(temp -> right) st.push(temp -> right);
if(temp -> left) st.push(temp -> left);
}
return result;
}
};

c++实现（中序遍历）左，中，右

一直向左走到底（入栈），遇到空就弹出栈顶（即“回溯”），访问该节点，然后转向其右子树。

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
//这个循环是为了使用cur
while(cur != NULL || !st.empty()){
if(cur != nullptr){
st.push(cur);
cur = cur -> left;//左
}else{
cur = st.top();
st.pop();
result.push_back(cur -> val);//中
cur = cur -> right;//右
}
}
return result;
}
};

• 因为栈放进去之后，所有元素都没有区别，只有栈顶获取，弹出，所以需要另一个指针来确定栈顶的元素是否要使用

c++实现（后序遍历）左，右，中

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root == nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* temp = st.top();
st.pop();
result.push_back(temp -> val);
//因为要保证使用顺序是先中，所以把左右中看作中右左的逆序。
if(temp -> left) st.push(temp -> left);
if(temp -> right) st.push(temp -> right);
}
//整体反转
reverse(result.begin(), result.end());
return result;
}
};

二叉树的统一迭代法

卡哥文字以及视频讲解链接

重点

• 两种方法
• 第一种，一个节点可以处理的范围是自己和左右孩子（该节点的根，该节点处理不到）。节点分两部分完成遍历，第一次通过节点来获得左右孩子，第二次看到第一次处理过的标志直接处理本节点。
• 第二种，给一个pair，first表示节点，second表示是否使用过。
• 本质是一种方式，就是让节点分两步进行。没处理过的先处理，处理过的直接用。

c++实现 （前序遍历）使用null表示使用

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root == nullptr) return {};//检查非空
st.push(root);//还是和while搭配
while(!st.empty()){
TreeNode* temp = st.top();
//每次进入首先获取栈顶元素
if(temp){
st.pop();
//因为是前序，需要弹出重新排一下序
if(temp -> right) st.push(temp -> right);
if(temp -> left) st.push(temp -> left);
st.push(temp);
st.push(nullptr);
//在要使用元素后加一个 NULL 表示这个节点和周围的父子关系已经实现过了，下一次就是使用
}else{
//栈顶为空，弹出，获得新栈顶，使用
st.pop();
temp = st.top();
st.pop();
result.push_back(temp -> val);
}
}
return result;
}
};

c++实现 (中序遍历）使用null表示使用

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

c++实现 (后序遍历）使用null表示使用

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(root == nullptr) return {};
st.push(root);
while(!st.empty()){
TreeNode* temp = st.top();
if(temp){
//这里不用弹出
st.push(nullptr);
if(temp -> right) st.push(temp -> right);
if(temp -> left) st.push(temp -> left);
}else{
st.pop();
temp = st.top();
st.pop();
result.push_back(temp -> val);
}
}
return result;
}
};

c++实现 (中序遍历）使用 pair 携带一个bool来确定元素状态

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<pair<TreeNode*, bool>> st;
if (root != nullptr)
st.push(make_pair(root, false)); // 多加一个参数，false 为默认值，含义见下文注释

while (!st.empty()) {
auto node = st.top().first;
auto visited = st.top().second; //多加一个 visited 参数，使“迭代统一写法”成为一件简单的事
st.pop();

if (visited) { // visited 为 True，表示该节点和两个儿子位次之前已经安排过了，现在可以收割节点了
result.push_back(node->val);
continue;
}

// visited 当前为 false, 表示初次访问本节点，此次访问的目的是“把自己和两个儿子在栈中安排好位次”。

// 中序遍历是'左中右'，右儿子最先入栈，最后出栈。
if (node->right)
st.push(make_pair(node->right, false));

// 把自己加回到栈中，位置居中。
// 同时，设置 visited 为 true，表示下次再访问本节点时，允许收割。
st.push(make_pair(node, true));

if (node->left)
st.push(make_pair(node->left, false)); // 左儿子最后入栈，最先出栈
}

return result;
}
};

二叉树层序遍历

卡哥文字以及视频讲解链接

重点

• 逐层

c++实现

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> result;
if(root == nullptr) return result;
que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
for(int i = 0 ; i < size ; i++){
TreeNode* temp = que.front();
que.pop();
vec.push_back(temp -> val);
if(temp -> left) que.push(temp -> left);
if(temp -> right) que.push(temp -> right);
}
result.push_back(vec);
}
return result;
}
};

一个重点

• 也是特点吧
• 遍历的时候，如果单一使用栈或者队列，函数体内的循环逻辑围绕的就是栈或队列是否为空
• 如果是中序迭代，遍历需要一个指针来辅助，函数体内的循环逻辑围绕的就是栈是否空以及指针是否为空
• 这样便于记忆二叉树的遍历逻辑

坚持就是胜利

• 第十三天，搞定！

author