在线甜品网站开发书,医学关键词 是哪个网站做,国家工商企业信用信息公示系统,小程序公司有必要做吗引子#xff1a;我们在之前学过c语言的二叉树#xff0c;但是c来做更好#xff01;本期要讲的题目如下(其实有点拖欠了#xff0c;很久之前#xff0c;就想写这个了#xff0c;今天终于克服自己的欲望#xff0c;达成了这个愿望#xff09;
1#xff0c; 二叉树创建字…引子我们在之前学过c语言的二叉树但是c来做更好本期要讲的题目如下(其实有点拖欠了很久之前就想写这个了今天终于克服自己的欲望达成了这个愿望
1 二叉树创建字符串 思路基于前序遍历考虑括号的是否可删除情况如果左为空但是右不为空则不能删除否则不能确定原先顺序其他括号直接删掉
代码
class Solution {
public:string tree2str(TreeNode* root) {string answer;if(rootnullptr)return answer;answerto_string(root-val);if(root-left!nullptr ||root-right){answer(;answertree2str(root-left);answer);}//if(root-right)if(root-right!nullptr){answer(;answertree2str(root-right);answer);}return answer;}
}; 2 二叉树的分层遍历1 思路借助每一次插入数组size就是每一层的元素个数每一层数据存储在一个一维顺序表中
然后利用queue队列来进行临时工具过度
代码
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint answer;if (root nullptr) {return answer;}size_t size 0;queueTreeNode* h;if (root) {h.push(root);size 1;}while (size) {vectorint c;while (size--) {TreeNode* front h.front();h.pop();c.push_back(front-val);if (front-left) {h.push(front-left);}if (front-right) {h.push(front-right);}}size h.size();answer.push_back(c);}return answer;}
}; 3 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 思路观察特征发现最近的公共祖先是p,q在二侧直接进行判断就行
或利用二条路径的相交点就是最近的公共祖先
代码
class Solution {
public:bool is_intree(TreeNode* root, TreeNode* x) {if (root nullptr) {return false;}return root x || is_intree(root-left, x) ||is_intree(root-right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root nullptr) {return nullptr;}if (root q || root p) {return root;}bool qleft is_intree(root-left, q);bool qright !qleft;bool pleft is_intree(root-left, p);bool pright !pleft;if (qleft pright || qright pleft) {return root;} else if (qleft pleft) {return lowestCommonAncestor(root-left, p, q);} else {return lowestCommonAncestor(root-right, p, q);}}
}; 4 二叉树搜索树转换成排序双向链表 思路进行遍历的同时修改指向可以有一个前驱节点提前知道自己的未来是什么或知道后面指向那里再进行left等赋予节点
代码
class Solution {public:// TreeNode* Left(TreeNode*t)// {// while(t-left)// {// tt-left;// }// return t;// }void INOrder(TreeNode* cur, TreeNode* prev) {if (cur nullptr) {return;}INOrder(cur-left, prev);cur-left prev;if (prev) {prev-right cur;}prev cur;INOrder(cur-right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {//TreeNode*headLeft(pRootOfTree);if (pRootOfTree nullptr) {return nullptr;}TreeNode* prev nullptr;INOrder(pRootOfTree, prev);TreeNode*headpRootOfTree;while(head-left){headhead-left;}while(prev!head){prevprev-left;}// prev-righthead;// head-leftprev;return prev;}
};5. 根据一棵树的前序遍历与中序遍历构造二叉树 思路前序根左右中序左根右在inoreder里面找根节点以根节点位置以左是左子树以右为右子树递归实现
代码
class Solution {
public:TreeNode* answer(vectorint preorder, vectorint inorder, int t,int lefti, int righti) {if (leftirighti) {return nullptr;}TreeNode* root new TreeNode(preorder[t]);int v lefti;while (v righti) {if (inorder[v] preorder[t]) {break;} else {v;}}t;root-left answer(preorder, inorder, t, lefti, v - 1);root-right answer(preorder, inorder, t, v 1, righti);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;return answer(preorder, inorder, i, 0, inorder.size() - 1);}
}; 6. 二叉树的前序遍历非递归迭代实现 思路利用栈的特点先遍历左节点在找左节点的右子树或右节点栈为空或curnullptr为结束条件
代码
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* h;vectorint answer;TreeNode*curroot;while(cur || !h.empty()){while(cur){h.push(cur);answer.push_back(cur-val);curcur-left;}TreeNode* toph.top();h.pop();curtop-right; }return answer;}
}; 希望帮到大家其他的题知识大同小异
