前言
更完两期二叉树的知识之后，来做几道oj题巩固一下基础
一、翻转二叉树
链接：leetcode链接
还是分治思想，将问题分解成左子树和右子树交换，遇到空树停止
采用递归算法做题
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr)
return nullptr;
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
二、另一棵树的子树
链接：leetcode链接
我们可以分解子问题，是不是当前树的子树，是不是左子树的子树，是不是右子树的子树。
细节：如果不是当前树的子树，不应该返回false，而应该继续在左右子树寻找
bool isSame(TreeNode* a,TreeNode* b)
{
if(a == nullptr && b == nullptr)
return true;
if(a == nullptr || b == nullptr)
return false;
if(a->val != b->val)
return false;
return isSame(a->left,b->left)
&& isSame(a->right,b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root == nullptr)
return false;
if(root->val == subRoot->val)
{
bool ret = isSame(root,subRoot);
if(ret) return true;
}
return isSubtree(root->left,subRoot)
|| isSubtree(root->right,subRoot);
}
三、二叉树的构建及遍历
链接：牛客链接
思路：
中序遍历很简单，很容易实现
这里，比较难的地方是，如何从先序遍历的序列中构建出二叉树
ok，我的思路是这样的：
先去构建当前树，再去构建左子树，再去构建右子树，符合先序遍历的顺序
很明显，这又是一个递归算法。
那么核心就是如何构建好当前树
遇到‘#’，就代表遇到空节点，遇到其他字符，就正常构建
注意：要传参控制string的下标，不然，没办法结束。
#include <iostream>
using namespace std;
struct TreeNode
{
TreeNode* left = nullptr;
TreeNode* right = nullptr;
char val;
};
TreeNode* Creater(string& s,int& i)
{
TreeNode* root = new TreeNode;
if(s[i] == '#')
{
i++;
return nullptr;
}
root->val = s[i++];
root->left = Creater(s, i);
root->right = Creater(s, i);
return root;
}
void InOrder(TreeNode* root)
{
if(root == nullptr)
return ;
InOrder(root->left);
cout << root->val << " ";
InOrder(root->right);
}
int main() {
string s;
cin >> s;
int i = 0;
TreeNode* root = Creater(s,i);
InOrder(root);
cout << endl;
return 0;
}
四、对称二叉树链接：
链接：leetcode链接
思路：我们这样想，如何比较两棵树是否对称呢？
记为root_a树和root_b树
显然，需要
(1) root_a树的根节点与root_b树的根节点值相等
(2) 需要root_a树的左子树和root_b树的右子树相等
(3) 需要root_a树的右子树和root_b树的左子树相等
空树为最小子问题
bool isMirror(TreeNode* left, TreeNode* right) {
if(left == nullptr && right == nullptr)
return true;
if(left == nullptr || right == nullptr)
return false;
if(left->val != right->val)
return false;
return isMirror(left->left,right->right)
&& isMirror(left->right,right->left);
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr)
return true;
return isMirror(root->left,root->right);
}
五、层序遍历
链接：leetcode链接
注意：该题目不仅仅是层序遍历，另外要求将每一层分开输出。
核心点在于，如何在层序遍历时区分二叉树每一层
层序遍历时的规律：
用队列存储节点，
可以发现，每次出完一层之后，
恰好下一层的所有节点正好进入队列
也就是队列中剩余元素的个数就是下一层的节点的个数
（读者可尝试自己画图分析）
依照次规律，我们可以另外设置一个变量，来记录每一层需要输出的个数。
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if(root == nullptr)
return {};
vector<vector<int>> vv;
q.push(root);
int levelSize = 1;
while(!q.empty())
{
vector<int> v;
while(levelSize--)
{
TreeNode* front = q.front();
q.pop();
v.push_back(front->val);
if(front->left) q.push(front->left);
if(front->right) q.push(front->right);
}
levelSize = q.size();
vv.push_back(v);
}
return vv;
}
六、判断是不是完全二叉树
链接：牛客链接
思路：
根据完全二叉树层序遍历的规律
出完上一层的同时，下一层全部进入队列
所以，我们可以这么操作
我们不管出队列的节点的左节点和右节点是否为nullptr，都进入队列。
当我们出到nullptr的时候，我们就跳出循环
去检查队列中剩余的元素
如果有非空元素，则并不是完全二叉树，如果全部都是空，则是完全二叉树。
为什么可以这么操作呢？
当我们出到nullptr的时候，如果后面有非空节点，那么他一定是nullptr节点前面节点的子节点，他一定进入了队列。
（这点理解清楚，这道题目就没问题了，读者可以画图尝试理解）
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode* front = q.front();
q.pop();
if(front != nullptr)
{
q.push(front->left);
q.push(front->right);
}
else break;
}
while(!q.empty())
{
TreeNode* front = q.front();
if(front != nullptr)
return false;
q.pop();
}
return true;
}
ok，先讲着6个题目吧，后面更复杂的题目，会在后续博客中进行更新
