手做网站,涟水建设银行网站,wordpress 手机端页面,浙江网站建设哪家好1判断完全二叉树递归做法
有四种情况#xff1a;1 左树完全#xff0c;右数满#xff0c;且左高为右高加一
2左满 #xff0c;右满#xff0c;左高为右高加一
3左满#xff0c;右完全#xff0c;左右高相等
4左右均满且高相等
#includeiostream
#include1 左树完全右数满且左高为右高加一
2左满 右满左高为右高加一
3左满右完全左右高相等
4左右均满且高相等
#includeiostream
#includealgorithm
using namespace std;
class TreeNode {
public:int val;TreeNode* left;TreeNode* right;TreeNode(int a) :val(a), left(nullptr), right(nullptr) {};
};
struct info {int height;bool iscbt;bool isfull;info(int a,bool b,bool c):height(a),iscbt(b),isfull(c){}
};
info process(TreeNode* head)
{if (head nullptr)return info(0, true, true);info leftinfo process(head-left);info rightinfo process(head-right);int height max(leftinfo.height, rightinfo.height) 1;bool isfull leftinfo.isfull rightinfo.isfull leftinfo.height rightinfo.height;bool iscbt false;if (leftinfo.isfull rightinfo.isfull leftinfo.height - rightinfo.height 1)iscbt true;if (leftinfo.isfull rightinfo.isfull leftinfo.height rightinfo.height )iscbt true;if (leftinfo.iscbt rightinfo.isfull leftinfo.height - rightinfo.height 1)iscbt true;if (leftinfo.isfull rightinfo.iscbt leftinfo.height rightinfo.height)iscbt true;return info(height, iscbt, isfull);
}
bool iscbt(TreeNode* head)
{if (head nullptr)return true;return process(head).iscbt;
}
2 给定一棵二叉树的头节点head返回这颗二叉树中最大的二叉搜索子树的头节点
#include iostream
#include vector
#include algorithm
using namespace std;
class TreeNode {
public:int val;TreeNode* left;TreeNode* right;TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};
struct info {TreeNode* node;//最大搜索子树头结点int maxsize;int min;int max;info(TreeNode *a,int b,int c,int d):node(a),maxsize(b),min(c),max(d){}
};
info* process(TreeNode* head)
{if (head nullptr)return nullptr;info* leftinfo process(head-left);info* rightinfo process(head-right);int maxval head-val;int minval head-val;TreeNode* ans nullptr;int size 0;if (leftinfo ! nullptr){maxval max(maxval, leftinfo-max);minval min(minval, leftinfo-min);ans leftinfo-node;size leftinfo-maxsize;}if (rightinfo ! nullptr){maxval max(maxval, rightinfo-max);minval min(minval, rightinfo-min);if (rightinfo-maxsize size){ans rightinfo-node;size rightinfo-maxsize;}}//当能构成搜索二叉树时if((leftinfonullptr?true:(leftinfo-nodehead-leftleftinfo-maxhead-val)) (rightinfo nullptr ? true : (rightinfo-node head-right rightinfo-min head-val))){anshead;//一定要记得判空size (leftinfo nullptr ? 0 : leftinfo-maxsize) (rightinfo nullptr ? 0 : leftinfo-maxsize) 1;}return new info(ans, size, minval, maxval);
}
TreeNode* maxSubBSTHead2(TreeNode* head)
{if (head nullptr)return nullptr;return process(head)-node;
}3给定一棵二叉树的头节点head和另外两个节点a和b返回a和b的最低公共祖先
法1用哈希表记下所有节点父节点将一个节点不停地向上这其中经过的节点放入一个集合中
再在另一个节点从上遍历一遍查找是否在集合中已经存在过找到的第一个即为答案
#include iostream
#include unordered_map
#include unordered_set
using namespace std;
class TreeNode {
public:int val;TreeNode* left;TreeNode* right;TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};
void fillmap(TreeNode* head, unordered_mapTreeNode*, TreeNode* map)
{if (head-left ! nullptr){map[head-left] head;fillmap(head-left, map);}if (head-right ! nullptr){map[head-right] head;fillmap(head-right, map);}
}
TreeNode* lowestAncestor(TreeNode* head, TreeNode* p, TreeNode* q)
{if (head nullptr)return nullptr;unordered_mapTreeNode*, TreeNode* map;//记录所有节点的父节点map[head] nullptr;fillmap(head,map);unordered_setTreeNode* set;TreeNode* cur p;set.insert(cur);while (map[cur] ! nullptr){cur map[cur];set.insert(cur);}cur q;while (set.find(cur) set.end()){cur map[cur];}return cur;
}
法二递归套路会聚点与x有关还是无关无关已经在左或右树右答案或这棵树a,b没找全
x是答案左发现一个右发现一个
x本身就是a然后左右发现了b x本身就是b左右发现a #include iostream
using namespace std;// 节点类
class Node {
public:int value;Node* left;Node* right;Node(int data) : value(data), left(nullptr), right(nullptr) {}
};
// 最低公共祖先函数
Node* lowestAncestor2(Node* head, Node* a, Node* b) {return process(head, a, b).ans;
}// 信息结构体
struct Info {bool findA;bool findB;Node* ans;Info(bool fA, bool fB, Node* an) : findA(fA), findB(fB), ans(an) {}
};// 处理函数
Info process(Node* x, Node* a, Node* b) {if (x nullptr) {return Info(false, false, nullptr);}Info leftInfo process(x-left, a, b);Info rightInfo process(x-right, a, b);bool findA (x a) || leftInfo.findA || rightInfo.findA;//不要忘了x本身就是a的情况bool findB (x b) || leftInfo.findB || rightInfo.findB;Node* ans nullptr;if (leftInfo.ans ! nullptr) {ans leftInfo.ans;}else if (rightInfo.ans ! nullptr) {ans rightInfo.ans;}else {if (findA findB) {ans x;}}return Info(findA, findB, ans);
}4 派对的最大快乐值 员工信息的定义如下: class Employee { public int happy; // 这名员工可以带来的快乐值 ListEmployee subordinates; // 这名员工有哪些直接下级 } 公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树 树的头节点是公司唯一的老板除老板之外的每个员工都有唯一的直接上级 叶节点是没有任何下属的基层员工(subordinates列表为空)除基层员工外每个员工都有一个或多个直接下级 这个公司现在要办party你可以决定哪些员工来哪些员工不来规则 1.如果某个员工来了那么这个员工的所有直接下级都不能来 2.派对的整体快乐值是所有到场员工快乐值的累加 3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点boss请返回派对的最大快乐值。
分情况:x来,x不来定义一个结构体保存两个值x来时候的最大值x不来时候的最大值
#includeiostream
#includealgorithm
#includevector
using namespace std;
struct employee {int happy;vectoremployee* nexts;employee(int h):happy(h),nexts(){}
};
struct info {int yes;int no;info(int a,int b):yes(a),no(b){}
};
info process(employee* head)
{if (head nullptr)return info(0, 0);int yes head-happy;int no 0;for (employee* a : head-nexts){info nextinfo process(a);yes nextinfo.no;no max(nextinfo.yes, nextinfo.no);}return info(yes, no);
}
int maxhappy(employee* head)
{info allinfo process(head);return max(allinfo.no, allinfo.yes);
}
5给定一个由字符串组成的数组strs必须把所有的字符串拼接起来返回所有可能的拼接结果中字典序最小的结果
贪心局部最小得全体最优解有时候可能会有错 字典序字符串排大小长度一样比数字大小
长度不同较短的补上最小的阿斯克码值然后与长的比较 证明过程得先证明排序过程具有传递性 像石头剪刀布就没有传递性 #include iostream
#include vector
#include algorithm
using namespace std;
class compare {
public:bool operator()(string a, string b){return (a b) (b a);}
};
string lowestString(vectorstring str)
{if (str.empty())return ;sort(str.begin(), str.end(), compare());string a;for (string c : str){a c;}return a;
}
