注册网站不用手机短信验证的,六安网络推广公司,医院网站建设的要求,wordpress 数据库下载根据二叉树创建字符串 本题的关键在于什么情况要省略括号#xff0c;什么情况不能省略#xff1a; 左右为空可以省略括号 左不为空#xff0c;右为空可以省略括号左为空,右不为空不能省略括号
class Solution {
public://1.左右为空可以省略括号//2.左不为空#xff0c;右…
根据二叉树创建字符串 本题的关键在于什么情况要省略括号什么情况不能省略 左右为空可以省略括号 左不为空右为空可以省略括号左为空,右不为空不能省略括号
class Solution {
public://1.左右为空可以省略括号//2.左不为空右为空可以省略括号//3.左为空,右不为空不能省略括号string tree2str(TreeNode* root) {string ret;if (root nullptr){return ret;}ret to_string(root-val);if (root-left || root-right){ret (;ret tree2str(root-left);ret );}if (root-right){ret (;ret tree2str(root-right);ret );}return ret;}
}; 二叉树的层序遍历 层序遍历咋一看很简单借助队列就能实现但是关键在于如何把每一层的结点区分开来放到不同的vector中。这里采用的方法是使用一个计数器count来记录本层的结点数count减到0时本层结点已经遍历完了此时队列中的就是下一层的结点用队列的元素个数更新count即可。
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint ret;if (root nullptr){return ret;}queueTreeNode* q;q.push(root);int count 1;//记录本层的结点数while (!q.empty()){vectorint v;while (count--){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);}}ret.push_back(v);count q.size();}return ret;}
}; 二叉树的最近公共祖先
思路找到根结点到p结点和q结点的路径对比两个路径即可得到答案时间复杂度O(n)
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vectorTreeNode* pPath;vectorTreeNode* qPath;findPath(root, p, pPath);findPath(root, q, qPath);int minSize min(pPath.size(), qPath.size());int i 0;for (; i minSize; i){if (pPath[i] ! qPath[i]){break;}}return pPath[i - 1];}bool findPath(TreeNode* root, TreeNode* target, vectorTreeNode* path){if (root nullptr){return false;}path.push_back(root);if (root target){return true;}if (findPath(root-left, target, path)){return true;}if (findPath(root-right, target, path)){return true;}//回溯--恢复现场path.pop_back();return false;}
};
二叉搜索树转双向链表 要将二叉搜索树转换为有序的双向链表那么肯定与中序遍历有关。中序遍历过程中用prev记录上一个遍历的结点cur记录当前结点prev-right cur, cur-left prev即可。
class Solution {
public:void InOrderConvert(TreeNode* cur, TreeNode* prev){if (cur nullptr){return;}InOrderConvert(cur-left, prev);cur-left prev;if (prev){prev-right cur;}prev cur;InOrderConvert(cur-right, prev);}TreeNode* Convert(TreeNode* pcurOfTree) {TreeNode* ret pcurOfTree;if (ret nullptr){return ret;}//找到最小的结点--也就是重新链接后双链表的头结点while (ret-left){ret ret-left;}TreeNode* prev nullptr;InOrderConvert(pcurOfTree, prev);return ret;}
};根据前序序列与中序序列构建二叉树 手工构建二叉树很容易本题难点在于如何将手动构建的过程转化成代码。想一想手工构建的过程。如何确定二叉树的根结点看前序序列。如何确定左右子树有哪些结点看中序序列。如何构建左右子树呢 先确定根节点这样又转化成了第一个问题。
牢记这一点前序序列确定根结点。中序序列确定左右子树有哪些结点。怎么表示左右子树的结点用一个区间标识范围即可。
class Solution {
public:TreeNode* _buildTree(vectorint preorder, vectorint inorder, int prei, int inbegin, int inend){//中序序列区间不存在if (inbegin inend){return nullptr;}//根据前序序列确定根结点TreeNode* root new TreeNode(preorder[prei]);prei;//根据中序序列确定左右子树的结点int pos inbegin;while (pos inend) {if (root-val inorder[pos]){break;}pos;}//[inbegin, pos - 1] [pos 1, inend]root-left _buildTree(preorder, inorder, prei, inbegin, pos - 1);root-right _buildTree(preorder, inorder, prei, pos 1, inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int prei 0;return _buildTree(preorder, inorder, prei, 0, inorder.size()- 1);}
};
根据后序序列和中序序列构建二叉树 思路和上一题类似不过要注意postorder要从后往前遍历并且要先构建右子树再构建左子树。
class Solution {
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {int posti postorder.size() - 1;return _buildTree(inorder, postorder, posti, 0, inorder.size() - 1);}TreeNode* _buildTree(vectorint inorder, vectorint postorder, int posti, int inbegin, int inend){if (inbegin inend){return nullptr;}//后序序列确定根节点TreeNode* root new TreeNode(postorder[posti]);posti--;//中序序列确定左右子树int pos inbegin;while (pos inend){if (root-val inorder[pos]){break;}pos;}//[inbegin, pos - 1] [pos 1, inend]//构建右子树和左子树root-right _buildTree(inorder, postorder, posti, pos 1, inend);root-left _buildTree(inorder, postorder, posti, inbegin, pos - 1);return root;}
};
二叉树的前序遍历迭代版本 递归写法很简单如何用迭代来完成呢
将一颗树分为左路结点和左路结点的右子树遍历到一颗树的左路结点时就访问它并将它放入栈中继续访问下一个左路结点。当左路结点访问完后从栈中取结点该结点就是最近的一个左路结点接下来访问它的右子树又回到了最开始的步骤。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint ret;TreeNode* cur root;while (cur || !st.empty()){//遍历左路结点并访问while (cur){ret.push_back(cur-val);st.push(cur);cur cur-left;}//遍历左路结点的右子树TreeNode* top st.top();cur top-right;st.pop();}return ret;}
};
二叉树的中序遍历迭代版本 和上一题类似一颗树看作左路结点和左路结点的右子树和前序遍历不同的是结点的访问时机不同。前序遍历是遍历到某个结点时就要访问它而中序遍历遍历到某个结点时先不访问将它存入栈中当再把它从栈中取出来时代表它的左子树已经访问过了接下来要访问右子树此时就是访问该结点的时机。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint ret;TreeNode* cur root;while (cur || !st.empty()){//遍历左路结点while (cur){st.push(cur);cur cur-left;}TreeNode* top st.top();st.pop();//访问左路结点ret.push_back(top-val);//遍历左路结点的右子树cur top-right;}return ret;}
};
二叉树的后序遍历迭代版本 同样一棵树分为左路结点和左路结点的右子树。左路结点的访问访问时机和前两道题又有所不同。遍历到左路结点时将它存入栈中不能访问当它的左子树遍历完时从栈中取出此时还是不能访问要取遍历它的右子树访问完右子树后再次从栈中取出此时才能访问并出栈。
本题难点在于当你把结点从栈中取出来时你如何知道它的右子树是否已经访问了呢此时应该访问这个结点还是暂时不访问去遍历它的右子树呢有两种方案
1.设置flag值标记结点的右子树是否已经访问。
要让每一个结点都对应一个flag值怎么做到呢很简单再建立一个栈类型为bool当结点入栈时bool类型的变量也跟着入栈(注意不是同一个栈)初始值为false。当从栈中取出结点时也把对应的bool变量取出如果为false说明右子树还没有遍历将bool变量置为true访问右子树若为true说明右子树已经遍历访问结点并出栈同时将bool变量也出栈。结点入栈bool变量入栈结点出栈bool变量也出栈这样一来就能做到一一对应了。
lass Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;stackbool flag;vectorint ret;TreeNode* cur root;while (cur || !st.empty()){//遍历左路结点while (cur){st.push(cur);flag.push(false);cur cur-left;}TreeNode* top st.top();if (top-right nullptr || flag.top() true){//访问左路结点ret.push_back(top-val);st.pop();flag.pop();}else{//遍历左路结点的右子树flag.top() true;cur top-right;}}return ret;}
};
2.标记前一个访问的结点
如果一个结点的右子树 (非空) 遍历完了那么上一个访问的结点一定是该结点的右孩子。根据这一规律只需创建一个prev变量来记录上一个访问的结点。如果一个结点从栈中取出来若该结点右子树为空则可以直接访问若该结点右子树不为空且上一个访问的结点是该结点的右孩子则也可以访问否则就要先访问该结点的右子树。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ret;stackTreeNode* st;TreeNode* cur root;TreeNode* prev nullptr;while (cur || !st.empty()){//遍历左路结点while (cur){st.push(cur);cur cur-left;}TreeNode* top st.top();if (top-right nullptr || top-right prev){//访问左路结点ret.push_back(top-val);st.pop();prev top;}else{//遍历右子树cur top-right;}}return ret;}
};
