剑指offer-树相关
2024-08-26 23:45:33
树相关
1.重建二叉树
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size() == || vin.size() == )
return nullptr;
return constructCore(pre, vin, , pre.size()-, , vin.size()-);
}
TreeNode* constructCore(vector<int> pre,vector<int> vin, int sp, int ep, int si, int ei)
{
//sp, ep 确定先序中树的范围，si，ei确定中序的子树范围
//先序头就是根
int rootValue = pre[sp];
TreeNode* root = new TreeNode(rootValue);
if(sp == ep)
{
if(si == ei && pre[sp] == vin[si])
return root;
}
//中序找到根，分为左右子树
int index = si;
while(index <= ei && vin[index] != rootValue)
++index;
int leftLen = index-si;//左子树长度
if(leftLen > )
{
root->left = constructCore(pre, vin, sp+, sp+leftLen, si, index-);
}
if(leftLen < ep-sp)
{
root->right = constructCore(pre, vin, sp+leftLen+, ep, index+, ei);
}
return root;
}
};
2.树的子结构
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//tree2空或者tree1空都不符合,问清楚空树是不是子树
if(pRoot2 == nullptr || pRoot1 == nullptr)
return false;
bool res = false;
if(pRoot1 != nullptr && pRoot2 != nullptr)
{
if(pRoot1->val == pRoot2->val)//找到匹配的根
res = isSubTree(pRoot1, pRoot2);
if(!res)//未找到，递归左节点
res = HasSubtree(pRoot1->left, pRoot2);
if(!res)//未找到，递归节点
res = HasSubtree(pRoot1->right, pRoot2);
}
return res;
}
//判断是否是子树
bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//tree2先遍历结束，重合
if(pRoot2 == nullptr)
return true;
//主树先结束，不重合
if(pRoot1 == nullptr)
return false;
//对于节点值不等，不重合
if(pRoot1->val != pRoot2->val)
return false;
//节点值相等，递归判断左右子树
return isSubTree(pRoot1->left, pRoot2->left)
&& isSubTree(pRoot1->right, pRoot2->right);
}
};
3.二叉树镜像
class Solution {
public:
void Mirror(TreeNode *pRoot) {
//前序遍历（根左右）树每个节点，如果节点有子节点，就交换子节点，直到叶子节点
//处理空树
if(pRoot == nullptr)
return;
//到达叶子节点
if(pRoot->left == nullptr && pRoot->right == nullptr)
return;
//交换子节点
TreeNode* tmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmp;
//递归左子树
if(pRoot->left)
Mirror(pRoot->left);//不要return，因为void不返回
//递归右子树
if(pRoot->right)
Mirror(pRoot->right);
}
};
4.对称二叉树
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetrical(pRoot, pRoot);
}
bool isSymmetrical(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1 == nullptr && pRoot2 == nullptr)//都空，对称
return true;
if(pRoot1 == nullptr || pRoot2 == nullptr)//一空一不空。不对称
return false;
if(pRoot1->val != pRoot2->val)//都不空，值不等，不对称，写了return true就无法再往下遍历了
return false;
//都不空，且值相等，在比较下一个节点
return isSymmetrical(pRoot1->left, pRoot2->right)
&& isSymmetrical(pRoot1->right, pRoot2->left);
}
};
5.二叉树前中后续遍历，递归和循环版
递归就是递归，循环实现用栈（前序中序比较简单，后续的话需要简单修改一下前序遍历，反转即可）
前序遍历非递归版
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode *root) {
if(!root)
return {};
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
auto p = s.top();
s.pop();
res.push_back(p->val);
if(p->right)
s.push(p->right);
if(p->left)
s.push(p->left);
}
return res;
}
};
6.后序遍历非递归版
class Solution {
public:
//一个巧妙地算法，先序遍历:根->左->右，根据出栈顺序根->右->左reverse,变成 左->右->根
vector<int> res;
vector<int> postorderTraversal(TreeNode *root) {
if(root == nullptr)
return {};
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
auto p = s.top();
s.pop();
res.push_back(p->val);
if(p->left)
s.push(p->left);
if(p->right)
s.push(p->right);
}
reverse(res.begin(), res.end());
return res;
}
};
7.二叉树中和为某值的路径
class Solution {
public:
vector<vector<int> > res;
//递归解决，防止段错误
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root == nullptr)
return res;
vector<int> cur;
find(root, expectNumber, cur);
return res;
}
void find(TreeNode* root, int target, vector<int> cur)
{
if(root == nullptr)
return ;
cur.push_back(root->val);
if((target-root->val) == && root->left == nullptr && root->right == nullptr)
res.push_back(cur);
else
{
if(root->left)
find(root->left, target-root->val, cur);
if(root->right)
find(root->right, target-root->val, cur);
}
}
};
8.二叉树的深度
（递归）
class Solution {
public:
int res = ;
int TreeDepth(TreeNode* pRoot)
{
int depth = ;
getDepth(pRoot, depth);
return res;
}
//递归函数，每遇到null节点说明到底了，更新res
void getDepth(TreeNode* root, int depth)
{
if(root == nullptr)
{
res = (depth > res) ? depth : res;
return ;
}
else
{
getDepth(root->left, depth+);
getDepth(root->right, depth+);
}
}
};
非递归（使用队列BFS层序遍历 数层数）
class Solution {
public:
//非递归，使用BFS栈来解决问题,其中的打印内容可以辅助查看具体过程
int TreeDepth(TreeNode *pRoot)
{
if (pRoot == nullptr)
return ;
queue<TreeNode *> s;
s.push(pRoot);
int depth = ;
while (!s.empty())
{
depth++;
int len = s.size();
cout << "第" << depth << "层，共有节点：" << len << "个" << endl;
for (int i = ; i < len; i++)
{
auto p = s.front();
s.pop();
cout << p->val << "出栈" << endl;
if (p->left)
{
s.push(p->left);
cout << p->left->val << "入栈" << endl;
}
if (p->right)
{
s.push(p->right);
cout << p->right->val << "入栈" << endl;
}
}
}
return depth;
}
};
9.二叉树的最小深度（使用队列来实现,将上面一个算法简单改改即可：在第一次左右子节点都不存在时，跳出即可）
class Solution {
public:
//那我也用层序遍历(BFS)试试吧
int run1(TreeNode *root) {
if(root == nullptr)
return ;
queue<TreeNode*> q;
q.push(root);
int depth = ;
while(!q.empty())
{
depth++;
int len = q.size();
for(int i=; i<len; i++)
{
auto p = q.front();
q.pop();
if(p->left == nullptr && p->right == nullptr)
return depth;
if(p->left)
q.push(p->left);
if(p->right)
q.push(p->right);
}
}
return depth;
}
//从上述方法我们可以想到，求算二叉树深度，也可以采用此法，跟我们原来的做法略有不同
//神奇的递归做法
int run(TreeNode *root) {
if(root == nullptr)
return ;
int l = run(root->left);
int r = run(root->right);
if(l == || r == )
return +l+r;
else
return +min(l, r);
}
};
序列化和反序列化二叉树
最新文章
- gulp es7配置文件
- (转载)构建public APIs与CORS
- Linux 路线 推荐
- [backbone] Getting Started with Backbone.js
- 解决tomcat部署多个虚拟机时报IllegalStateException: Web app root system property already set to 的问题
- Chapter Schema
- Oracle基础（十） DML数据操作
- FFT多项式乘法加速
- _js day9
- LCM Cardinality
- fileZilla 设置 记录一笔 以防忘记
- MPEG2_TS流基本概念和数据结构
- myCat知识笔记
- Nginx+tomcat组合实现高并发场景的动静分离和负载均衡方案
- Linux-Ubuntu14.04下mongodb安装部署
- arcgis for silverlight 地图放大到某个点或者几何对象
- 使用matplotlib画双纵轴坐标
- Asp.Net Core跨域配置
- C#显示接口实现和隐式接口实现
- [转载]看看大牛们是怎样获得英文综述（reviews）的?