北京企业建设网站公司,常见的网络直接营销有哪些,wordpress静态链接,精仿虎嗅网织梦网站模板一、根据二叉树创建字符串
题目描述#xff1a; 给你二叉树的根节点 root #xff0c;请你采用前序遍历的方式#xff0c;将二叉树转化为一个由括号和整数组成的字符串#xff0c;返回构造出的字符串。 空节点使用一对空括号对 “()” 表示#xff0c;转化后需要省略所有…一、根据二叉树创建字符串
题目描述 给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。 空节点使用一对空括号对 “()” 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 题目示例
分析 根据题意我们可以观察出一下规律
根据题意如果左子树为空右子树不为空就需要加空()如果右子树为空就不需要加空()左右子树都为空就不需要加空()
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:string str ;string tree2str(TreeNode* root) {if (root nullptr)return ;str to_string(root-val);//根据题意如果左子树为空右子树不为空就需要加空()//如果右子树为空就不需要加空()//左右子树都为空就不需要加空()if (root-left || root-right){str (;tree2str(root-left);str );}if (root-right){str (;tree2str(root-right);str );}return str;}
};二、二叉树的层序遍历
题目描述 给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 题目示例
分析 通过层序遍历二叉树我们可以通过队列来实现利用队列先进先出的特点对二叉树进行层序遍历,控制每一层的节点的个数来实现层序遍历。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint vv;queueTreeNode* q;int levelsize 0;if(root){levelsize 1;q.push(root);}while(q.size()){vectorint v;while(levelsize--){TreeNode* front q.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}levelsize q.size();vv.push_back(v);}return vv;}
};三、二叉树的层序遍历 II
题目描述 给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 题目示例
分析 思路和上面一样只需要将上面返回的vector数组逆转就行
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint vv;queueTreeNode* q;int levelsize 0;if(root){levelsize 1;q.push(root);}while(q.size()){vectorint v;while(levelsize--){TreeNode* front q.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}levelsize q.size();vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};四、二叉树的最近公共祖先
题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。 题目示例
分析
第一种思路时间复杂度O(N^2) 我们可以通过观察规律发现两个节点要不分布在最近祖先的两个不同的子树中要不分布在最近祖先的同一个子树中包含祖先于是我们就可以遍历树中的每一个节点如果祖先的左右子树中是否有这两个节点或如果祖先本身就是需要查找的节点就只需要看左子树或右子树是否存在另一个节点如果有就证明其是最近的公共祖先。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool IsIntree(TreeNode* root,TreeNode* p,TreeNode* q){if(root nullptr)return false;if(root-val p-val || root-val q-val)return true;bool left IsIntree(root-left,p,q);bool right IsIntree(root-right,p,q);return left || right;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr)return nullptr;//p是自己的祖然后在查找q是否在左子树或右子树if(root-val p-val (IsIntree(root-left,p,q) || IsIntree(root-right,p,q))){return root;}//q是自己的祖然后在查找p是否在左子树或右子树else if(root-val q-val (IsIntree(root-left,p,q) || IsIntree(root-right,p,q))){return root;}//p,q在不在左子树或右子树中的任意一棵树else if(IsIntree(root-left,p,q) IsIntree(root-right,p,q)){return root;}//这个节点不是最近公共祖先else {TreeNode* Inright lowestCommonAncestor(root-left,p,q);if(Inright)//不是nullptr就表示这个节点是最近公共祖先return Inright;TreeNode* Inleft lowestCommonAncestor(root-right,p,q);if(Inleft)//不是nullptr就表示这个节点是最近公共祖先return Inleft;return nullptr;}}
};第二种思路时间复杂度O(N) 通过前序遍历左子树和右子树找到对应的节点并用栈存储从根节点到对应节点的路劲最后模拟两个链表找交点的情况长的栈先出栈直到两个栈的大小相等在一起出栈直到两个出栈的节点值相等就表示其是最近的公共祖先
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool GetPath(TreeNode* root,TreeNode* node,stackTreeNode* Path){if(root nullptr)return false;Path.push(root);if(root node)return true;bool left GetPath(root-left,node,Path);bool right GetPath(root-right,node,Path);if(!right !left)Path.pop();return left || right;//左子树和右子树都没有找到}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* ppath,qpath;GetPath(root,p,ppath);GetPath(root,q,qpath);while(ppath.size() qpath.size()){ppath.pop();}while(qpath.size() ppath.size()){qpath.pop();}while(qpath.top() ! ppath.top()){qpath.pop();ppath.pop();}return ppath.top();}
};五、将二叉搜索树转化为排序的双向链表
题目描述 将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。 对于双向循环列表你可以将左右孩子指针作为双向循环链表的前驱和后继指针第一个节点的前驱是最后一个节点最后一个节点的后继是第一个节点。 特别地我们希望可以 就地 完成转换操作。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。 题目示例
分析 由题目给出条件可知该二叉树是二叉搜索树这题需要我们把二叉搜索树转换为 升序排列 的链表我们知道二叉搜索树的升序遍历是 中序遍历 于是我们就可以定义两个指针 cur 和 prev cur 指向当前节点 prev 指向当前节点的上一个节点通过 中序遍历 树的每一个节点当当前节点 cur 的左子树遍历完cur-left prev ,通过改变前驱和后继的指针的指向来把其链接已排序的双向循环链表.
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val _val;left NULL;right NULL;}Node(int _val, Node* _left, Node* _right) {val _val;left _left;right _right;}
};
*/
class Solution {
public:void Link(Node* cur,Node* prev){if(cur nullptr)return;Link(cur-left,prev);cur-left prev;if(prev)prev-right cur;prev cur;Link(cur-right,prev);}Node* treeToDoublyList(Node* root) {if(root nullptr)return nullptr;Node* cur root;Node* prev nullptr;Link(cur,prev);Node* tail prev;while(root-left){root root-left;}Node* head root;head-left tail;tail-right head;return head;}
};六、从前序与中序遍历序列构造二叉树
题目描述 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点 题目示例
分析 根据前序就可以确定根节点根据中序就可以确定根节点的左右子树用区间来表示根节点的左右子树区间最后就可以确定出整个二叉树。
class Solution {
public://pre_begin,pre_endTreeNode* buildTree_with_pre_in(vectorint preorder, vectorint inorder,int pospre,int in_begin,int in_end){if(in_begin in_end){return nullptr;}//if(pospre inorder.size() - 1)TreeNode* newnode new TreeNode(preorder[pospre]);int pos;for(int i in_begin;i in_end;i){if(inorder[i] newnode-val){pos i;break;}}if(pospre inorder.size() - 1)pospre inorder.size() - 1;TreeNode* left buildTree_with_pre_in(preorder,inorder,pospre,in_begin,pos - 1);// 左子树if(pospre inorder.size() - 1)pospre inorder.size() - 1;TreeNode* right buildTree_with_pre_in(preorder,inorder,pospre,pos 1,in_end);// 右子树newnode-left left;newnode-right right;return newnode;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;TreeNode* root buildTree_with_pre_in(preorder,inorder,i,0,inorder.size() - 1);return root;}
};七、从中序与后序遍历序列构造二叉树
题目描述 给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历,postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 题目示例
分析 与上面的题目类似只不过是后序遍历根据后序遍历的特点左子树-右子树-根节点的特点我们可以发现把后序反过来就可以确定根节点的位置然后再根据中序判断右子树和左子树的位置其实就是一个 根-右子树-左子树 的过程来创建树而前序创建树的就是 根-左子树-右子树 和前序相比就是遍历子树的顺序变了而已。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree_with_in_post(vectorint inorder,vectorint postorder,int pospost,int in_begin,int in_end){if(in_begin in_end)return nullptr;TreeNode* newnode new TreeNode(postorder[pospost--]);int pos -1;for(int i in_begin;i in_end;i){if(inorder[i] newnode-val){pos i;break;}}TreeNode* right buildTree_with_in_post(inorder,postorder,pospost,pos 1,in_end);TreeNode* left buildTree_with_in_post(inorder,postorder,pospost,in_begin,pos - 1);newnode-left left;newnode-right right;return newnode;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int i postorder.size() - 1;//从后序的最后一个节点开始TreeNode* root buildTree_with_in_post(inorder,postorder,i,0,postorder.size() - 1);return root;}
};八、非递归实现二叉树的前序遍历
题目描述 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 题目示例
分析 要迭代⾮递归实现⼆叉树前序遍历⾸先还是要借助递归的类似的思想只是需要把结点存在栈中⽅便类似递归回退时取父路径结点。跟这⾥不同的是这⾥把⼀棵⼆叉树分为两个部分
先访问左路结点再访问左路结点的右⼦树 这⾥访问右⼦树要以循环从栈依次取出这些结点循环⼦问题的思想访问左路结点的右⼦树。前序遍历的顺序为 根-左子树-右子树 我们每次访问一个节点后需要把它入栈就可以实现前序遍历。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint v;if(root nullptr)return v;stackTreeNode* st;st.push(root);v.emplace_back(root-val);while(root-left){root root-left;v.emplace_back(root-val);st.push(root);}while(st.size()){TreeNode* cur st.top();st.pop();cur cur-right;if(cur){st.push(cur);v.emplace_back(cur-val);}while(cur cur-left){cur cur-left;v.emplace_back(cur-val);st.push(cur);}}return v;}
};九、非递归实现二叉树的中序遍历
题目描述 给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 题目示例
分析 中序访问的顺序是 左子树-根-右子树 每当访问玩左子树的时候就将栈顶数据入栈即可实现中序遍历二叉树
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint v;if(root nullptr)return v;stackTreeNode* st;st.push(root);while(root-left){root root-left;st.push(root);}while(st.size()){TreeNode* cur st.top();v.emplace_back(cur-val); st.pop();cur cur-right;if(cur){st.push(cur);}while(cur cur-left){cur cur-left;st.push(cur);}}return v;}
};十、非递归实现二叉树的后序遍历
题目描述 给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 题目示例
分析: 后序遍历的需要先访问顺序为 左子树-右子树-根 首先我们先把根节点 root 左子树的节点全部加入栈我们想要访问根就必须先把根的左子树和右子树都访问完于是我们就需要用 prev 来表示它当前节点的前一个节点如果 cur-right nullptr || cur-right prev 就表示当前根节点的左子树和右子树都访问完了然后再出栈并且不需要向下访问了。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint v;if(root nullptr)return v;stackTreeNode* st;st.push(root);TreeNode* prev nullptr;while(root-left){root root-left;st.push(root);}while(st.size()){TreeNode* cur st.top();if(cur-right nullptr || cur-right prev){st.pop();v.emplace_back(cur-val);prev cur;continue;}cur cur-right;if(cur){st.push(cur);}while(cur cur-left){cur cur-left;st.push(cur);}}return v;}
};
