当前位置:首页 » 《我的小黑屋》 » 正文

移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——12.二叉树(习题)

11 人参与  2024年09月18日 08:03  分类 : 《我的小黑屋》  评论

点击全文阅读


1.根据二叉树创建字符串

. - 力扣(LeetCode)

d8620be55c1d41ff902d3ca31f0f69a8.png

我的思路:

1. 根节点单独讨论,因为,根节点之后才会开始有括号

2.根节点的左孩子和右孩子分别进入operation函数

 

operation函数:

1.如果root不为空,先加(,再加root->val

 

2.分类讨论:

 

1.if(root->left==NULL&&root->right==NULL)

如果为叶子节点:直接加)

2.if(root->left==NULL&&root->right!=NULL)

如果左为空,右不为空;

无法省略括号,需要加()

3.如果左右都不为空

递归

 operation(root->left,arr);

 operation(root->right,arr);

最后加)

 

 函数介绍:to_string,可将整形转换为string;

class Solution {public:     void operation(TreeNode* root,string& arr)     {        if(root)        {          arr.push_back('(');          arr+=to_string(root->val);          if(root->left==NULL&&root->right==NULL)          {             arr.push_back(')');          }          else          {             if(root->left==NULL&&root->right!=NULL)             {                arr.push_back('(');                arr.push_back(')');             }                            operation(root->left,arr);              operation(root->right,arr);              arr.push_back(')');          }        }     }    string tree2str(TreeNode* root) {     string arr;     if(root)     {        arr+=to_string(root->val);        if(root->left==NULL&&root->right!=NULL)        {                arr.push_back('(');                arr.push_back(')');        }        operation(root->left,arr);        operation(root->right,arr);     }     return arr;    }};

 2.二叉树的分层遍历1

 . - 力扣(LeetCode)

c666f0043cf645b8b647e330d6478af9.png

我的思路:

1. 建一个队列,并把根节点入队列,记录队列的大小;

2.while(size)

出队列,size--,并将左右节点入队列

3.size=队列的size;

4.若队列为空,则已经遍历完毕;

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) {     TreeNode* tmp;     vector<int> brr;     vector<vector<int>> arr;     queue<TreeNode*> it;     int size=0;     if(root!=NULL)     {       it.push(root);       size++;     }      while(it.size())      {        while(size)        {          tmp=it.front();          brr.push_back(tmp->val);          it.pop();          size--;          if(tmp->left)          {            it.push(tmp->left);          }          if(tmp->right)          {            it.push(tmp->right);          }        }        arr.push_back(brr);        brr.clear();        size=it.size();      }      return arr;    }};

 3.二叉树的分层遍历2

 . - 力扣(LeetCode)

 9c7a0a90bcfb4c079e84cf6c75c1727c.png

和前一题一样,只需在最后reverse(arr.begin(),arr.end()); 

class Solution {public:    vector<vector<int>> levelOrderBottom(TreeNode* root) {     TreeNode* tmp;     vector<int> brr;     vector<vector<int>> arr;     queue<TreeNode*> it;     int size=0;     if(root!=NULL)     {       it.push(root);       size++;     }      while(it.size())      {        while(size)        {          tmp=it.front();          brr.push_back(tmp->val);          it.pop();          size--;          if(tmp->left)          {            it.push(tmp->left);          }          if(tmp->right)          {            it.push(tmp->right);          }        }        arr.push_back(brr);        brr.clear();        size=it.size();      }      reverse(arr.begin(),arr.end());      return arr;    }};

 4.最近公共祖先

. - 力扣(LeetCode)

7fac6759f7494312bc79fec624af56fb.png

我的思路:

1.先写一个查找函数

2.从根节点开始查找p

3. 再从p开始查找q

如果找到了,返回p

如果没找到,那么p就变成p的父节点,再继续查找,直至从p可以找到q,返回p 

class Solution {public:      bool qfirstfind(TreeNode* p, TreeNode* q)      {        if(p==nullptr)        return false;        else if(p!=q)        {            if(qfirstfind(p->left, q))            return true;            else            return qfirstfind(p->right, q);        }        else if(p==q)        return true;                return 1;      }                          //这个函数用来查找p之下是否有q              void firstfind(TreeNode* p, TreeNode* q,TreeNode*&parent)      {        if(p!=nullptr)        {            if(p->left!=q&&p->right!=q)            {               firstfind(p->left, q,parent);               firstfind(p->right, q,parent);            }        else        {            parent=p;            //这里用来保存q的父节点        }        }      }       void secondfind(TreeNode* root, TreeNode*&p, TreeNode*&q)       {            TreeNode* it;            while((p->left!=q)&&(p->right!=q)&&(p!=root))            {                firstfind(root,p,it);                p=it;           //p赋值为其父节点                if(qfirstfind(p,q))                {                    break;                }            }       }    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        {            if(qfirstfind(p,q))            return p;            if(qfirstfind(q,p))            return q;                    //如果p,q有一个是公共祖先,则直接返回            secondfind(root, p, q);            return p;            }    }};

更好的的思路 !!!!!!!!:

用两个栈分别存放从根找到p,q的路径

1.若两个栈大小不一致

则用pop函数,保证二者大小一致

2.若两栈的top不一致,则二者都pop

直至两者的top相同,返回二者的top,即为最近的公共祖先

class Solution {public:     bool findpath(TreeNode* root, TreeNode* x,stack<TreeNode*>&path)     {        if(root==nullptr)        return false;        path.push(root);             if(root==x)        return true;                if(findpath(root->left,x,path))        return true;        if(findpath(root->right,x,path))        return true;        path.pop();     //走到这一步,证明root的左右子树都没有x,所以要把root删除        return false;     }    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        stack<TreeNode*> ppath,qpath;        findpath(root,p,ppath);        findpath(root,q,qpath);        while(ppath.size()!=qpath.size())        {            if(ppath.size()>qpath.size())            ppath.pop();            else            qpath.pop();        }                while(ppath.top()!=qpath.top())        {             ppath.pop();             qpath.pop();        }         return ppath.top();    }};

5.二叉树搜索树转换成排序双向链表 

二叉搜索树与双向链表_牛客题霸_牛客网

b168c86260684d6589f5ad6340d0c3c3.png

我的思路:

1.find1函数:寻找左子树中的最大值

2.find2函数:寻找右子树中的最小值

3.find3函数:寻找头节点,即二叉树中的最小值 

从叶子节点开始连接

class Solution {public:    void creat(TreeNode*root){if(root!=nullptr)         {if(root->left==nullptr&&root->right==nullptr) {return; }          else{             TreeNode*qleft=root->left;             TreeNode*qright=root->right;            creat(qleft);creat(qright);             TreeNode*nleft=find1(root);             TreeNode*nright=find2(root); if(nleft)     nleft->right=root; if(nright)     nright->left=root;     root->left=nleft;     root->right=nright;  } }} TreeNode*find1(TreeNode*root) { TreeNode*it = root->left;   if(it)            //左右都不为空,找左子树最大的    {while (it->right)      {  it = it->right;      }  return it;}else {return nullptr;} }TreeNode*find2(TreeNode*root) { TreeNode*it = root->right;  //左右都不为空,找右子树最小的 if(it)      {while (it->left)       {     it = it->left;       }return it;  }  else {  return nullptr;  } }TreeNode*find3(TreeNode*root) {            //找根    TreeNode* it=root;    while (it->left)    {  it = it->left;    }return it; }    TreeNode* Convert(TreeNode* pRootOfTree) {        if(pRootOfTree==nullptr)return pRootOfTree;TreeNode*head=find3(pRootOfTree);        creat(pRootOfTree);        return head;    }};

6.前序中序还原二叉树 

 . - 力扣(LeetCode)

bbeef85ffb954846ac18574de210af4c.png

思路:

1.preorder 确定根

2.确定根了之后,将inorder分成两部分,左边为左子树,右边为右子树

3.分别递归左边和右边

 

class Solution {public:    TreeNode* creat(vector<int>& preorder, vector<int>& inorder,int &prev,int begin,int end)    {        TreeNode* root;        if(begin>end)        return nullptr;        int flag=preorder[prev];        int i=0;       while(flag!=inorder[i])       {         i++;       }        root=new TreeNode(flag);        prev++;       root->left=creat(preorder,inorder,prev,begin,i-1);  //前序遍历,根左右,根后是左子树,所以先构建左子树       root->right=creat(preorder,inorder,prev,i+1,end);   //有点类似并归排序       return root;    }    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {    TreeNode* root;    int prev=0;     //前序遍历,从头开始找根    root=creat(preorder,inorder,prev,0,preorder.size()-1);    return root;    }};

7.中序和后序还原二叉树 

. - 力扣(LeetCode)

 1d28c53684c1410a8ea35b8324b4a303.png

和上一题一样,中序确定左右子树

但不同的是得从后序遍历的尾开始找根,且根前是右子树 

class Solution {public: TreeNode* creat(vector<int>& postorder, vector<int>& inorder,int &prev,int begin,int end)    {        TreeNode* root;        if(begin>end)        return nullptr;        int flag=postorder[prev];        int i=0;       while(flag!=inorder[i])       {         i++;       }        root=new TreeNode(flag);        prev--;       root->right=creat(postorder,inorder,prev,i+1,end);   //后序遍历左右根,倒着找的话,根的前面是右子树,所以右子树先建立       root->left=creat(postorder,inorder,prev,begin,i-1);       return root;    }        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {    TreeNode* root;    int prev=inorder.size()-1;   //从尾开始找根    root=creat(postorder,inorder,prev,0,inorder.size()-1);    return root;    }};

 

 

 

 

 

 

 

 


点击全文阅读


本文链接:http://zhangshiyu.com/post/161058.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1