wordpress实现新闻列表,烟台网站排名优化公司哪家好,全国工商登记网,做dj网站创建二叉树、遍历二叉树、二叉树的最近公共祖先任何疑问、意见、建议请公众号留言或联系qq474356284先序、后序创建二叉树先中后层序遍历二叉树二叉树的最近公共祖先 输入格式#xff1a;创建二叉树时的输入#xff1a;如序列#xff1a;{1 2 -1 -1 3 -1 -1}表示1结点有2,… 创建二叉树、遍历二叉树、二叉树的最近公共祖先任何疑问、意见、建议请公众号留言或联系qq474356284先序、后序创建二叉树先中后层序遍历二叉树二叉树的最近公共祖先 输入格式创建二叉树时的输入 如序列{1 2 -1 -1 3 -1 -1}表示1结点有2,3两个孩子2,3结点没有孩子。 如序列{3 5 6 -1 -1 2 7 -1 -1 4 -1 -1 1 9 -1 -1 8 -1 -1}其中-1表示结点为空。需注意已知先中、中后序可确定唯一二叉树先后序不能确定唯一二叉树。(这里指的是遍历后的序列而不是这里输入时的序列因为输入时的序列含有空节点已经含有二叉树的所有信息)输入样例先序创建二叉树1 2 -1 -1 3 -1 -13 5 6 -1 -1 2 7 -1 -1 4 -1 -1 1 9 -1 -1 8 -1 -1后序创建二叉树-1 -1 2 -1 -1 3 1-1 -1 6 -1 -1 7 -1 -1 4 2 5 -1 -1 9 -1 -1 8 1 3求两节点最近的公共祖先2 35 1输出样例先序1 2 3中序2 1 3后序2 3 1先序1 2 3中序2 1 3后序2 3 1先序3 5 6 2 7 4 1 9 8中序6 5 7 2 4 3 9 1 8后序6 7 4 2 5 9 8 1 3最近公共祖先13解决方法待补充。2021校招金山云9.16笔试题最近公共祖先(须自己创建二叉树)(1)代码实现#include #include #include #include #include #include #include #include using namespace std;//一航代码//树节点定义(此处与leetcode定义保持一致)struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(NULL), right(NULL){}//初值列};//创建二叉树//先中-√ 先后-× 中后-√class creat_tree {public: //先序创建一棵树 void creatpre(TreeNode** root){ /*如序列{1 2 -1 -1 3 -1 -1}表示1结点有2,3两个孩子2,3结点没有孩子。 如序列{3 5 6 -1 -1 2 7 -1 -1 4 -1 -1 1 9 -1 -1 8 -1 -1}*/ int val; cin val; if (val -1) root nullptr; else { *root new TreeNode(val); creatpre(((*root)-left)); creatpre(((*root)-right)); } } //后序创建一棵树 void creatpost(TreeNode** root, vectorint t, bool flag){ /*如序列{-1 -1 2 -1 -1 3 1}表示1结点有2,3两个孩子2,3结点没有孩子。 如序列{-1 -1 6 -1 -1 7 -1 -1 4 2 5 -1 -1 9 -1 -1 8 1 3}*/ int val; char ch; if (flag) { //flag标记第一次获取二叉树序列 while (cin val) { t.push_back(val); if ((ch getchar()) \n) break; } flag false; } static int count t.size(); val t[--count]; if (val -1) root nullptr; else { *root new TreeNode(val); creatpost(((*root)-right), t, flag); creatpost(((*root)-left), t, flag); } }};//先中后三种递归遍历方式class traversal_rec {public: vectorint ans; vectorint preorder(TreeNode* root) { if (root NULL) return ans; ans.push_back(root-val); preorder(root-left); preorder(root-right); return ans; } vectorint inorder(TreeNode* root) { if (root NULL) return ans; inorder(root-left); ans.push_back(root-val); inorder(root-right); return ans; } vectorint posorder(TreeNode* root) { if (root NULL) return ans; posorder(root-left); posorder(root-right); ans.push_back(root-val); return ans; }};//先中后三种迭代遍历二叉树参考https://mp.weixin.qq.com/s/WKg0Ty1_3SZkztpHubZPRgclass traversal_ite {public: vectorint res; //保存结果 vectorint preorder(TreeNode* root) { stack call; //调用栈 if (root ! nullptr) call.push(root); //首先介入root节点 while (!call.empty()) { TreeNode* t call.top(); call.pop(); //访问过的节点弹出 if (t ! nullptr) { if (t-right) call.push(t-right); //右节点先压栈最后处理 if (t-left) call.push(t-left); call.push(t); //当前节点重新压栈(留着以后处理)因为先序遍历所以最后压栈 call.push(nullptr); //在当前节点之前加入一个空节点表示已经访问过了 } else { //空节点表示之前已经访问过了现在需要处理除了递归之外的内容 res.push_back(call.top()-val); // call.top()是nullptr之前压栈的一个节点也就是上面call.push(t)中的那个t call.pop(); //处理完了第二次弹出节点(彻底从栈中移除) } } return res; } vectorint inorder(TreeNode* root) { stack call; if (root ! nullptr) call.push(root); while (!call.empty()) { TreeNode* t call.top(); call.pop(); if (t ! nullptr) { if (t-right) call.push(t-right); call.push(t); //在左节点之前重新插入该节点以便在左节点之后处理(访问值) call.push(nullptr); //nullptr跟随t插入标识已经访问过还没有被处理 if (t-left) call.push(t-left); } else { res.push_back(call.top()-val); call.pop(); } } return res; } vectorint postorder(TreeNode* root) { stack call; if (root ! nullptr) call.push(root); while (!call.empty()) { TreeNode* t call.top(); call.pop(); if (t ! nullptr) { call.push(t); //在右节点之前重新插入该节点以便在最后处理(访问值) call.push(nullptr); //nullptr跟随t插入标识已经访问过还没有被处理 if (t-right) call.push(t-right); if (t-left) call.push(t-left); } else { res.push_back(call.top()-val); call.pop(); } } return res; }};//层序遍历二叉树class level_order {public: vectorvectorint levelOrder(TreeNode* root) { queue que; if (root ! NULL) que.push(root); vectorvectorint result; while (!que.empty()) { int size que.size(); vectorint vec; for (int i 0; i size; i) { // 这里一定要使用固定大小size不要使用que.size()因为que.size是不断变化的 TreeNode* node que.front(); que.pop(); vec.push_back(node-val); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } result.push_back(vec); } return result; }};// p结点与q结点的最近公共祖先TreeNode* lowc(TreeNode* root, int p, int q){ if (root nullptr) return 0; if (root-val p || root-val q) return root; TreeNode* rleft lowc(root-left, p, q); TreeNode* rright lowc(root-right, p, q); if (rleft ! nullptr rright ! nullptr) return root; else if (rright ! nullptr) return rright; else return rleft; return nullptr;}int main(){ creat_tree creat; TreeNode* root; //先序创建二叉树 creat.creatpre(root); //后序创建二叉树 // vector tree; // creat.creatpost(root, tree, true); traversal_rec rec; vectorint res rec.preorder(root); // vector res rec.inorder(root); // vector res rec.posorder(root); traversal_ite ite; // vector res ite.preorder(root); // vector res ite.inorder(root); // vector res ite.postorder(root); for (int i 0; i (int)res.size(); i) {//注意最后一个节点输出后面有空格 cout res[i] ; } cout endl; // level_order level; //层序输出 // vector res level.levelOrder(root); // for(int i 0;i (int)res.size();i){ // for(int j 0;j (int)res[i].size();j){ // cout res[i][j] ; // } // } //求二叉树结点pq最近的公共祖先 int p, q; cin p q; TreeNode *t lowc(root, p, q); cout t-val endl; return 0;}
