C/C++每日一练(20230326) 二叉树专场(3)
目录
1. 二叉树的前序遍历 🌟🌟
1. 二叉树的前序遍历
给你二叉树的根节点 root
,返回它节点值的 前序 遍历。
示例 1:
输入:root = [1,null,2,3] 输出:[1,2,3]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
示例 4:
输入:root = [1,2] 输出:[1,2]
示例 5:
输入:root = [1,null,2] 输出:[1,2]
提示:
- 树中节点数目在范围
[0, 100]
内 -100 <= Node.val <= 100
进阶:递归算法很简单,你可以通过迭代算法完成吗?
出处:
https://edu.csdn.net/practice/23819517
代码: 递归算法
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
private:
void rec(TreeNode *root, vector<int> &ret)
{
if (root != nullptr)
{
ret.push_back(root->val);
rec(root->right, ret);
rec(root->left, ret);
}
}
public:
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> ret;
rec(root, ret);
return ret;
}
};
string Vector2String(vector<int> vect) {
stringstream ss;
ss << "[";
for (size_t i = 0; i < vect.size(); i++)
{
ss << to_string(vect[i]);
ss << (i < vect.size() - 1 ? "," : "]");
}
return ss.str();
}
int main()
{
TreeNode *root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
Solution s;
cout << Vector2String(s.postorderTraversal(root)) << endl;
return 0;
}
输出:
[2,1,3]
进阶: 迭代算法
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#define null INT_MIN
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& nums)
{
if (nums.empty()) return nullptr;
TreeNode *root = new TreeNode(nums.front());
queue<TreeNode*> q;
q.push(root);
int i = 1;
while(!q.empty() && i < nums.size())
{
TreeNode *cur = q.front();
q.pop();
if(i < nums.size() && nums[i] != null)
{
cur->left = new TreeNode(nums[i]);
q.push(cur->left);
}
i++;
if(i < nums.size() && nums[i] != null)
{
cur->right = new TreeNode(nums[i]);
q.push(cur->right);
}
i++;
}
return root;
}
void preorderPrint(TreeNode* root) {
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (node != nullptr) {
cout << node->val << " ";
st.push(node->right);
st.push(node->left);
}
}
cout << endl;
}
void preorderPrint2(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while (node != nullptr || !st.empty()) {
while (node != nullptr) {
cout << node->val << " ";
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
node = node->right;
}
cout << endl;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (node != nullptr) {
res.push_back(node->val);
st.push(node->right);
st.push(node->left);
}
}
return res;
}
vector<int> preorderTraversal2(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* node = root;
while (node != nullptr || !st.empty()) {
while (node != nullptr) {
res.push_back(node->val);
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
node = node->right;
}
return res;
}
string vectorToString(vector<int> vect) {
stringstream ss;
ss << "[";
for (size_t i = 0; i < vect.size(); i++)
{
ss << (vect[i] == null ? "null" : to_string(vect[i]));
ss << (i < vect.size() - 1 ? "," : "]");
}
return ss.str();
}
int main()
{
vector<int> nums = {1,null,2,3};
TreeNode *root = buildTree(nums);
preorderPrint(root);
preorderPrint2(root);
cout << vectorToString(preorderTraversal(root)) << endl;
cout << vectorToString(preorderTraversal2(root)) << endl;
nums = {3,9,20,null,null,15,7};
root = buildTree(nums);
preorderPrint(root);
preorderPrint2(root);
cout << vectorToString(preorderTraversal(root)) << endl;
cout << vectorToString(preorderTraversal2(root)) << endl;
nums = {1,2,3,4,5,6,7};
root = buildTree(nums);
preorderPrint(root);
preorderPrint2(root);
cout << vectorToString(preorderTraversal(root)) << endl;
cout << vectorToString(preorderTraversal2(root)) << endl;
return 0;
}
输出:
1 2 3
1 2 3
[1,2,3]
[1,2,3]
3 9 20 15 7
3 9 20 15 7
[3,9,20,15,7]
[3,9,20,15,7]
1 2 4 5 3 6 7
1 2 4 5 3 6 7
[1,2,4,5,3,6,7]
[1,2,4,5,3,6,7]
中序后序对比:
//中序遍历
void inorder(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
cout << node->val << " ";
node = node->right;
}
}
//后序遍历
void postorder(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
TreeNode* last = nullptr;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
st.push(node);
node = node->left;
}
node = st.top();
if (node->right == nullptr || node->right == last) {
cout << node->val << " ";
st.pop();
last = node;
node = nullptr;
} else {
node = node->right;
}
}
}
2. 二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
出处:
https://bbs.csdn.net/topics/604364348
代码:
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#define null INT_MIN
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
stack<pair<TreeNode*, int>> s;
int maxDep = 0;
s.push(make_pair(root, 1));
while (!s.empty()) {
TreeNode* cur = s.top().first;
int curDep = s.top().second;
s.pop();
if (cur) {
maxDep = max(maxDep, curDep);
s.push(make_pair(cur->left, curDep + 1));
s.push(make_pair(cur->right, curDep + 1));
}
}
return maxDep;
}
};
TreeNode* buildTree(vector<int>& nums)
{
if (nums.empty()) return nullptr;
TreeNode *root = new TreeNode(nums.front());
queue<TreeNode*> q;
q.push(root);
int i = 1;
while(!q.empty() && i < nums.size())
{
TreeNode *cur = q.front();
q.pop();
if(i < nums.size() && nums[i] != null)
{
cur->left = new TreeNode(nums[i]);
q.push(cur->left);
}
i++;
if(i < nums.size() && nums[i] != null)
{
cur->right = new TreeNode(nums[i]);
q.push(cur->right);
}
i++;
}
return root;
}
int main()
{
Solution s;
vector<int> nums = {3,9,20,null,null,15,7};
TreeNode *root = buildTree(nums);
cout << s.maxDepth(root) << endl;
nums = {1,null,2,null,3,null,4};
root = buildTree(nums);
cout << s.maxDepth(root) << endl;
return 0;
}
输出:
3
4
递归法:
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#define null INT_MIN
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
int ldepth = maxDepth(root->left);
int rdepth = maxDepth(root->right);
return max(ldepth, rdepth) + 1;
}
};
TreeNode* buildTree(vector<int>& nums)
{
if (nums.empty()) return nullptr;
TreeNode *root = new TreeNode(nums.front());
queue<TreeNode*> q;
q.push(root);
int i = 1;
while(!q.empty() && i < nums.size())
{
TreeNode *cur = q.front();
q.pop();
if(i < nums.size() && nums[i] != null)
{
cur->left = new TreeNode(nums[i]);
q.push(cur->left);
}
i++;
if(i < nums.size() && nums[i] != null)
{
cur->right = new TreeNode(nums[i]);
q.push(cur->right);
}
i++;
}
return root;
}
int main()
{
Solution s;
vector<int> nums = {3,9,20,null,null,15,7};
TreeNode *root = buildTree(nums);
cout << s.maxDepth(root) << endl;
nums = {1,null,2,null,3,null,4};
root = buildTree(nums);
cout << s.maxDepth(root) << endl;
return 0;
}
3. 有序数组转换为二叉搜索树
给你一个整数数组 nums
,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1:
输入:nums = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] 解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
示例 2:
输入:nums = [1,3] 输出:[3,1] 解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums
按 严格递增 顺序排列
出处:
https://edu.csdn.net/practice/23819519
代码:
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#define null INT_MIN
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
TreeNode *sortedArrayToBST(vector<int> &nums)
{
return dfs(nums, 0, nums.size() - 1);
}
TreeNode *dfs(vector<int> &nums, int left, int right)
{
if (left > right)
return NULL;
int mid = (left + right) / 2;
TreeNode *t = new TreeNode(nums[mid]);
t->left = dfs(nums, left, mid - 1);
t->right = dfs(nums, mid + 1, right);
return t;
}
};
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (cur) {
res.push_back(cur->val);
q.push(cur->left);
q.push(cur->right);
} else {
res.push_back(null);
}
}
for(int i = res.size(); i > 0 && res[i-1] == null; i--)
res.pop_back();
return res;
}
string vectorToString(vector<int> vect) {
stringstream ss;
ss << "[";
for (size_t i = 0; i < vect.size(); i++)
{
ss << (vect[i] == null ? "null" : to_string(vect[i]));
ss << (i < vect.size() - 1 ? "," : "]");
}
return ss.str();
}
int main()
{
Solution s;
vector<int> nums = {-10,-3,0,5,9};
TreeNode *bst = s.sortedArrayToBST(nums);
cout << vectorToString(levelOrder(bst)) << endl;
nums = {1,3};
bst = s.sortedArrayToBST(nums);
cout << vectorToString(levelOrder(bst)) << endl;
return 0;
}
输出:
[0,-10,5,null,-3,null,9]
[1,null,3]
代码2:
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#define null INT_MIN
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.empty()) return nullptr;
int mid = nums.size() / 2;
TreeNode* root = new TreeNode(nums[mid]);
vector<int> left(nums.begin(), nums.begin() + mid);
vector<int> right(nums.begin() + mid + 1, nums.end());
root->left = sortedArrayToBST(left);
root->right = sortedArrayToBST(right);
return root;
}
};
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (cur) {
res.push_back(cur->val);
q.push(cur->left);
q.push(cur->right);
} else {
res.push_back(null);
}
}
for(int i = res.size(); i > 0 && res[i-1] == null; i--)
res.pop_back();
return res;
}
string vectorToString(vector<int> vect) {
stringstream ss;
ss << "[";
for (size_t i = 0; i < vect.size(); i++)
{
ss << (vect[i] == null ? "null" : to_string(vect[i]));
ss << (i < vect.size() - 1 ? "," : "]");
}
return ss.str();
}
int main()
{
Solution s;
vector<int> nums = {-10,-3,0,5,9};
TreeNode *bst = s.sortedArrayToBST(nums);
cout << vectorToString(levelOrder(bst)) << endl;
nums = {1,3};
bst = s.sortedArrayToBST(nums);
cout << vectorToString(levelOrder(bst)) << endl;
return 0;
}
输出:
[0,-3,9,-10,null,5]
[3,1]
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
![]() | Golang每日一练 专栏 |
![]() | Python每日一练 专栏 |
![]() | C/C++每日一练 专栏 |
![]() | Java每日一练 专栏 |
相关文章
- c++string截取字符串
- c++获取子类窗口句柄位置_C++中各种获取窗口句柄的方法「建议收藏」
- 【C++】string类的模拟实现
- Linus Torvalds:“C++ 真是一门很烂的语言!”
- c++二叉树的先序,中序,后序遍历_二叉树的构造
- C++学习(一五九)Qt的场景图Scene Graph
- C++ 快速理解数组名为何是常指针
- 论c++中的数组,vector和array的区别及用法
- C/C++ Qt TabWidget 实现多窗体创建
- c++的链表-C++链表
- c++的链表-链表入门(C++)
- C/C++ 调用API获取当前时间
- 数据结构小记【Python/C++版】——树与二叉树篇
- C++11 Lambda表达式
- 如何用Swift重写C++/ObjC代码库,并将其缩减70%
- C++ 测试框架 GoogleTest 初学者入门篇 丙
- C++ const常量在多文件编程中的3种用法
- C++ vector swap()去除多余容量(详解版)
- C++封装线程类的实现方法