目录
1. 翻转二叉树 🌟
2. 二叉树的最小深度 🌟
3. 填充每个节点的下一个右侧节点指针 🌟🌟
附：二叉树的序列化与反序列化
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
1. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9
输出：
4 / \ 7 2 / \ / \ 9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
出处：
https://edu.csdn.net/practice/27729560
代码：
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
TreeNode *invertTree(TreeNode *root)
{
if (!root)
{
return root;
}
TreeNode *temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
return root;
}
};输出：
2. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
提示：
- 树中节点数的范围在
[0, 105]内 -1000 <= Node.val <= 1000
代码：
#include <bits/stdc++.h>
#define null INT_MIN
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
int minDepth(TreeNode *root)
{
if (!root)
return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
return (left && right) ? 1 + min(left, right) : 1 + left + right;
}
};
TreeNode* buildTree(vector<int>& nums)
{
TreeNode *root = new TreeNode(nums[0]);
queue<TreeNode*> q;
q.push(root);
int i = 1;
while(!q.empty() && i < nums.size())
{
TreeNode *cur = q.front();
q.pop();
if(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> root = {3,9,20,null,null,15,7};
TreeNode* tree = buildTree(root);
cout << s.minDepth(tree) << endl;
root = {2,null,3,null,4,null,5,null,6};
tree = buildTree(root);
cout << s.minDepth(tree) << endl;
return 0;
} 输出：
2
5
3. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
提示：
- 树中节点的数量少于
4096 -1000 <= node.val <= 1000
出处：
https://edu.csdn.net/practice/27729558
代码：
#include <bits/stdc++.h>
using namespace std;
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)
{
if (!root)
return nullptr;
root->next = nullptr;
connect_helper(root);
return root;
}
private:
void connect_helper(Node *pNode)
{
if (!pNode)
return;
if (pNode->left == nullptr)
return;
pNode->left->next = pNode->right;
if (pNode->right == nullptr)
return;
if (pNode->next != nullptr)
pNode->right->next = pNode->next->left;
else
pNode->right->next = nullptr;
connect_helper(pNode->left);
connect_helper(pNode->right);
}
};输出：
附：二叉树的序列化与反序列化
class Codec
{
public:
string serialize(TreeNode *root)
{
string result = "[";
queue<TreeNode *> myQue;
myQue.push(root);
while (!myQue.empty())
{
root = myQue.front();
myQue.pop();
if (root == NULL)
{
result += "null,";
continue;
}
else
{
result += to_string(root->val) + ",";
myQue.push(root->left);
myQue.push(root->right);
}
}
if (result == "[null,")
{
result.resize(result.size() - 1);
}
else
{
int endIndex = result.size() - 1;
while (result[endIndex] < '0' || result[endIndex] > '9')
{
endIndex -= 1;
}
result.resize(endIndex + 1);
}
result += "]";
return result;
}
TreeNode *deserialize(string data)
{
vector<string> dataVec;
int dataSize = data.size();
for (int index = 1; index < dataSize - 1; ++index)
{
string tempData = "";
while (index < dataSize - 1 && data[index] != ',')
{
tempData += data[index++];
}
dataVec.push_back(tempData);
}
int dataVecSize = dataVec.size();
queue<TreeNode *> myQue;
if (dataVec[0] == "null")
{
return NULL;
}
TreeNode *result = new TreeNode(atoi(dataVec[0].c_str())), *tempPtr;
myQue.push(result);
for (int index = 1; index < dataVecSize; ++index)
{
tempPtr = myQue.front();
myQue.pop();
if (dataVec[index] != "null")
{
tempPtr->left = new TreeNode(atoi(dataVec[index].c_str()));
myQue.push(tempPtr->left);
}
index += 1;
if (index < dataVecSize && dataVec[index] != "null")
{
tempPtr->right = new TreeNode(atoi(dataVec[index].c_str()));
myQue.push(tempPtr->right);
}
}
return result;
}
};🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！ 文章来源：https://www.toymoban.com/news/detail-442681.html
☸ 主页：https://hannyang.blog.csdn.net/文章来源地址https://www.toymoban.com/news/detail-442681.html
 |
Golang每日一练 专栏 |
 |
Python每日一练 专栏 |
 |
C/C++每日一练 专栏 |
 |
Java每日一练 专栏 |
到了这里，关于C/C++每日一练(20230513) 二叉树专场（7）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
