买东西网站有哪些,免备案网站空间购买,网络建站网网络推广,wordpress菜单小工具栏1.根据二叉树创建字符串 力扣 给你二叉树的根节点 root #xff0c;请你采用前序遍历的方式#xff0c;将二叉树转化为一个由括号和整数组成的字符串#xff0c;返回构造出的字符串。 空节点使用一对空括号对 () 表示#xff0c;转化后需要省略所有不影响字符…1.根据二叉树创建字符串 力扣 给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。 空节点使用一对空括号对 () 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 来源力扣LeetCode class Solution {
public:string tree2str(TreeNode* root) {//根据前序遍历确定字符串if(rootnullptr)return ;string treeto_string(root-val);//只有左右子树都为空不保留括号其他情况都保留括号if(root-left||root-right){tree(;treetree2str(root-left);tree); }if(root-right){tree(;treetree2str(root-right);tree); }return tree;}
};
2.二叉树分层遍历 力扣 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1 输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]] 示例 2 输入root [1] 输出[[1]] 示例 3 输入root [] 输出[] 来源力扣LeetCode class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {//用队列来确定queueTreeNode* TreeNode1;vectorvectorint vv;int levesize0;if(root){TreeNode1.push(root);levesize1;}while(!TreeNode1.empty()){vectorint v;for(int i0;ilevesize;i){TreeNode* front TreeNode1.front();TreeNode1.pop();v.push_back(front-val);if(front-left){ TreeNode1.push(front-left);}if(front-right){TreeNode1.push(front-right);}}vv.push_back(v);//TreeNode.pop();levesizeTreeNode1.size();}return vv;}
};
3.二叉树的最近公共祖先 力扣 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3 输入root [1,2], p 1, q 2 输出1 来源力扣LeetCode class Solution {
public:bool find_node(TreeNode* root, TreeNode* p, stackTreeNode* path){if(rootnullptr)return false;path.push(root);if (root p)return true;if( find_node(root-left, p, path))return true;if( find_node(root-right, p, path))return true;path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){//使用两个栈存放二叉树要找的数据stackTreeNode* ppath;stackTreeNode* qpath;find_node(root, p, ppath);find_node(root, q, qpath);//确定长度while (ppath.size() qpath.size()){ppath.pop();}while (ppath.size() qpath.size()){qpath.pop();}while (ppath.size() qpath.size()){if (ppath.top() qpath.top()){return ppath.top();}ppath.pop();qpath.pop();}return nullptr;}
};
4. 二叉搜索树与双向链表_牛客题霸_牛客网 输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围输入二叉树的节点数 0≤n≤10000≤n≤1000二叉树中每个节点的值 0≤val≤10000≤val≤1000 要求空间复杂度O(1)O(1)即在原树上操作时间复杂度 O(n)O(n) 注意: 1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构 4.你不用输出双向链表程序会根据你的返回值自动打印输出 输入描述 二叉树的根节点 返回值描述 双向链表的其中一个头节点。 示例1 输入 {10,6,14,4,8,12,16} 返回值 From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4; class Solution {void Indor(TreeNode* cur,TreeNode* prev){//确定双向链表if(curnullptr)return;Indor(cur-left,prev);cur-leftprev;if(prev)prev-rightcur;prevcur;Indor(cur-right,prev);}
public:TreeNode* Convert(TreeNode* pRootOfTree){TreeNode* prevnullptr;Indor(pRootOfTree,prev);//判断头结点TreeNode* headpRootOfTree;while(headhead-left){headhead-left;}return head;}
};5.从前序与中序确定二叉树 力扣 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 示例 2: 输入: preorder [-1], inorder [-1] 输出: [-1] 来源力扣LeetCode class Solution {TreeNode* buildTree(vectorint preorder,vectorint inorder,int prie,int inbegin,int inend){if(inbegininend)//结束条件return nullptr;TreeNode* rootnew TreeNode(preorder[prie]);int rootiinbegin;while(rootiinend){if(preorder[prie]inorder[rooti])break;rooti;} prie;root-leftbuildTree(preorder,inorder,prie,inbegin,rooti-1);root-rightbuildTree(preorder,inorder,prie,rooti1,inend);return root;}public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i0;TreeNode* rootbuildTree(preorder,inorder,i,0,inorder.size()-1);return root;}
};
6.中序与后序确定二叉树 力扣
class Solution {TreeNode* _buildTree(vectorint inorder,vectorint postorder,int n,int inbegin,int inend){if(inbegininend)return nullptr;TreeNode* rootnew TreeNode(postorder[n]);int rootiinbegin;while(rootiinend){if(postorder[n]inorder[rooti])break;rooti;}n--;root-right_buildTree(inorder,postorder,n,rooti1,inend);//先右再左root-left_buildTree(inorder,postorder,n,inbegin,rooti-1);return root;}
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {int npostorder.size()-1;return _buildTree(inorder,postorder,n,0,postorder.size()-1);}
};
7.二叉树后序遍历迭代算法 力扣 给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 示例 1 输入root [1,null,2,3] 输出[3,2,1] 来源力扣LeetCode class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint nums;TreeNode* curroot;TreeNode* prevnullptr;while(cur||!st.empty()){while(cur){st.push(cur);curcur-left;}TreeNode* topst.top();if(top-rightnullptr||top-rightprev)//防止重复遍历{prevtop;st.pop();nums.push_back(top-val);}else{curtop-right;}}return nums;}
};
