代码随想录算法训练营：13/60

非科班学习算法day13 | LeetCode144:二叉树的前序遍历，Leetcode145: 二叉树的后序遍历，Leetcode97:二叉树的中序遍历，LeetCode589:N叉树的前序遍历，Leetcode102:二叉树的层序遍历，Leetcode199: 二叉树的右视图，Leetcode637: 二叉树的层平均值，Leetcode429: N叉树的层序遍历，Leetcode515: 在每个树行中找最大值，Leetcode116: 填充每个节点的下一个右侧节点指针

介绍

一、基础概念补充：

1.递归的三个步骤

二、LeetCode题目

1.LeetCode144:二叉树的前序遍历

题目解析

2.Leetcode145:二叉树的后序遍历

题目解析

3.Leetcode97: 二叉树的中序遍历

题目解析

4.Leetcode589: N叉树的前序遍历

题目解析

5.Leetcode102:二叉树的层序遍历

题目解析

6.Leetcode199: 二叉树的右视图

7.Leetcode637: 二叉树的层平均值

8.Leetcode429: N叉树的层序遍历

9.Leetcode515: 在每个树行中找最大值

10.Leetcode116: 填充每个节点的下一个右侧节点指针

总结

介绍

包含LC的几道题目，还有相应概念的补充。

一、基础概念补充：

1.递归的三个步骤

确定返回值和传入参数；

确定中止条件；

写一次递归的逻辑。

不要过分关注后面的过程，容易绕进去。

二、LeetCode题目

1.LeetCode144:二叉树的前序遍历

题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

题目解析

分别采用递归和迭代方法给出，其中递归分为引用函数的递归和直接递归。

第一种递归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) {}* };*/
class Solution {
public:// 设置递归函数vector<int> Traverasl(TreeNode* cur, vector<int>& vec) {// 设置中止出口if (cur == nullptr)return vec;// 递归体vec.push_back(cur->val);Traverasl(cur->left, vec);Traverasl(cur->right, vec);// 返回结果return vec;}vector<int> preorderTraversal(TreeNode* root) {// 创建vecvector<int> result;// 调用函数return Traverasl(root, result);}
};

第二种递归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) {}* };*/
class Solution {
public:vector<int> result;vector<int> preorderTraversal(TreeNode* root) { //设置中止出口if(root == nullptr) return result;//迭代体result.push_back(root->val);        //中preorderTraversal(root->left);      //左边遍历preorderTraversal(root->right);     //右边遍历//设置最终返回值return result;}
};

迭代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) {}* };*/
class Solution {
public:// 创建模拟栈stack<TreeNode*> st;// 创建结果vectorvector<int> result;// 迭代函数vector<int> preorderTraversal(TreeNode* root) {// 插入根节点if (root != nullptr)st.push(root);// 设置迭代条件while (!st.empty()) {// 记录栈顶TreeNode* cur_node = st.top();// 弹栈st.pop();// 中间节点进入结果vectorresult.push_back(cur_node->val);// 进栈该节点的左右子节点if (cur_node->right != nullptr)st.push(cur_node->right);if (cur_node->left != nullptr)st.push(cur_node->left);// 弹栈操作开始迭代}return result;}
};

2.Leetcode145:二叉树的后序遍历

题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

题目解析

分别采用递归和迭代方法给出，其中递归分为引用函数的递归和直接递归。

第一种递归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) {}* };*/
class Solution {
public:// 创建递归函数vector<int> Traversal(TreeNode* cur, vector<int>& vec) {// 设置中止条件if (cur == nullptr)return vec;// 递归体Traversal(cur->left, vec);Traversal(cur->right, vec);vec.push_back(cur->val);// 返回return vec;}vector<int> postorderTraversal(TreeNode* root) {// 创建结果函数vector<int> result;// 调用函数return Traversal(root, result);}
};

第二种递归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) {}* };*/
class Solution {
public://创建vecvector<int> result;vector<int> postorderTraversal(TreeNode* root) {//设置中止出口if(root == nullptr) return result;//递归体postorderTraversal(root->left);postorderTraversal(root->right);result.push_back(root->val);//返回return result;}
};

迭代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) {}* };*/
class Solution {
public:// 创建模拟栈stack<TreeNode*> st;// 创建结果vectorvector<int> result;vector<int> postorderTraversal(TreeNode* root) {// 初始化if (root != nullptr)st.push(root);// 迭代while (!st.empty()) {// 记录栈顶TreeNode* cur_node = st.top();// 弹栈st.pop();// 元素进入结果result.push_back(cur_node->val);// 加入左右子节点if (cur_node->left != nullptr)st.push(cur_node->left);if (cur_node->right != nullptr)st.push(cur_node->right);}reverse(result.begin(), result.end());return result;}
};

3.Leetcode97: 二叉树的中序遍历

题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

题目解析

分别采用递归和迭代方法给出，其中递归分为引用函数的递归和直接递归。

第一种递归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) {}* };*/
class Solution {
public:// 创建递归函数vector<int> Traversal(TreeNode* cur, vector<int>& vec) {// 设置递归出口if (cur == nullptr)return vec;// 递归体Traversal(cur->left, vec);vec.push_back(cur->val);Traversal(cur->right, vec);//return vec;}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;return Traversal(root, result);}
};

第二种递归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) {}* };*/
class Solution {
public://创建返回值vector<int> result;vector<int> inorderTraversal(TreeNode* root) {if(root == nullptr) return result;inorderTraversal(root->left);result.push_back(root->val);inorderTraversal(root->right);return result;}
};

注意点1：

4.Leetcode589: N叉树的前序遍历

题目链接：589. N 叉树的前序遍历 - 力扣（LeetCode）

题目解析

分别采用递归和迭代方法给出，其中递归分为引用函数的递归和直接递归。

递归C++代码如下：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:// 创建结果vectorvector<int> result;vector<int> preorder(Node* root) {// 创建中止出口if (root == nullptr)return result;// 递归体result.push_back(root->val);for (auto child : root->children) {preorder(child);}return result;}
};

迭代c++代码如下：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:stack<Node*> st;vector<int> result;vector<int> preorder(Node* root) {if (root == nullptr)return result;st.push(root);while (!st.empty()) {Node* cur_node = st.top();st.pop();result.push_back(cur_node->val);for (auto it = cur_node->children.rbegin();it != cur_node->children.rend(); it++) {st.push(*it);//vector<Node*>::reverse_iterator}}return result;}
};

5.Leetcode102:二叉树的层序遍历

题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

题目解析

下面的题目用的都是层序遍历，非常相似，只是在处理的时候可能有不同的统计变量或者操作，这里直接给出代码。

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) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {//建立数组接受结果vector<vector<int>> result;//建立控制队列queue<TreeNode*>que;//检验根节点是否为空if(root != nullptr){que.push(root);}//弹出控制队列的所有元素为止while(!que.empty()){//创建当前层数组接受结果vector<int> current_vec;//记录当前层数元素数量int size = que.size();//设置循环弹出当前层数量的元素for(;size > 0; size--){//记录元素即将弹出元素TreeNode* current_node = que.front();//将该元素记录到current_veccurrent_vec.push_back(current_node->val);//弹出que.pop();//添加左右节点if(current_node->left){que.push(current_node->left);}if(current_node->right){que.push(current_node->right);}}//当前层弹出结束，更新队列长度size = que.size();//将当前队列添加到结果result.push_back(current_vec);}return result;}
};

6.Leetcode199: 二叉树的右视图

题目链接：199. 二叉树的右视图 - 力扣（LeetCode）

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) {}* };*/
class Solution {
public:vector<int> rightSideView(TreeNode* root) {//创建结果数列vector<int> result;//创建队列queue<TreeNode*> que;//插入根节点if(root != nullptr) que.push(root);//初始化层元素数量int size = que.size();//循环弹出节点while(!que.empty()){for(int i = 0; i < size; i++){//记录头部TreeNode* cur_node = que.front();//弹出que.pop();//当到达最后一个,单次判断if(i == size - 1){result.push_back(cur_node->val);}//添加左右节点if(cur_node->left != nullptr) que.push(cur_node->left);if(cur_node->right != nullptr) que.push(cur_node->right);}//更新size = que.size();}return result;}
};

7.Leetcode637: 二叉树的层平均值

题目链接：637. 二叉树的层平均值 - 力扣（LeetCode）

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) {}* };*/
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {//创建结果数组vector<double> result;//创建队列queue<TreeNode*> que;//插入根节点if(root != nullptr) que.push(root);//初始化层元素数量int size = que.size();//循环弹栈while(!que.empty()){//初始化和double sum = 0.0;for(int i = 0; i < size; i++){//记录当前节点信息TreeNode* cur_node = que.front();//更新和sum += (double)cur_node->val;//弹栈que.pop();//加入子节点if(cur_node->left != nullptr) que.push(cur_node->left);if(cur_node->right != nullptr) que.push(cur_node->right);}//计算平均值double cur_avg = sum / size;//更新sizesize = que.size();//下一循环已经result.push_back(cur_avg);}return result;}
};

8.Leetcode429: N叉树的层序遍历

题目链接：429. N 叉树的层序遍历 - 力扣（LeetCode）

C++代码如下：

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector<vector<int>> levelOrder(Node* root) {//建立数组接受结果vector<vector<int>> result;//建立队列queue<Node*> que;//插入根节点if(root != NULL){que.push(root);}//初始化sizeint size = que.size();//循环while(!que.empty()){//建立当前层接收数组vector<int> cur_vec;while(size--){//保存栈顶Node* cur_node = que.front();//插入结果cur_vec.push_back(cur_node->val);//弹栈que.pop();//遍历插入子节点for(auto it:cur_node->children){if(it){que.push(it);}}}//更新size = que.size();result.push_back(cur_vec);  }return result;  }};

9.Leetcode515: 在每个树行中找最大值

题目链接：515. 在每个树行中找最大值 - 力扣（LeetCode）

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) {}* };*/
class Solution {
public:vector<int> largestValues(TreeNode* root) {//建立接受数组vector<int> result;//建立辅助队列queue<TreeNode*> que;//插入根节点if(root != nullptr){que.push(root);}//初始化数组长度int size = que.size();//循环while(!que.empty()){vector<int> cur_vec;while(size--){//保留头部信息TreeNode* cur_node = que.front();//弹栈que.pop();//插入cur_vec.push_back(cur_node->val);//左右子节点if(cur_node->left != nullptr) que.push(cur_node->left);if(cur_node->right != nullptr) que.push(cur_node->right);}//更新sizesize = que.size();//maxauto it = max_element(cur_vec.begin(), cur_vec.end());int vec_max = *it;//max to reresult.push_back(vec_max);}return result;}
};

10.Leetcode116: 填充每个节点的下一个右侧节点指针

题目链接：116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

C++代码如下：

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {// 创建辅助队列queue<Node*> que;// 插入根节点if (root != NULL) {que.push(root);}// 初始化数组长度int size = que.size();// 设置循环while (!que.empty()) {while (size--) {// 记录当前头节点Node* cur_node = que.front();// 弹栈que.pop();// 记录当前头节点Node* cur_node2 = que.front();// 设置指向if (size == 0) {cur_node->next = NULL;} else {cur_node->next = cur_node2;}if (cur_node->left)que.push(cur_node->left);if (cur_node->right)que.push(cur_node->right);}// 更新sizesize = que.size();}return root;}
};