当前位置： 首页 > article >正文

数据结构二叉树进阶

article 2025/4/2 3:39:35

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

1.题目

2. 分析原理

要把二叉树元素按照前序顺序取出来，并且以字符串的形式返回，还要添加括号对于左子树和右子树，那么第一步就是向定义一个string类型来接收取出的元素，需要用到to_string函数把整型变成string类型，第二步就是递归来深度遍历了，但是需要判断一下，题目有些情况是省略了括号，有些没有省去，题目例子可以知道左为空右不为空就不能省略括号，左不为空右为空就可以省略括号，所以遍历左子树就要left||right，这样包含了对左为空右不为空的情况，遍历右子树深度时只需要判断root->right存不存在就行，不在就之间省略括号。

3.代码实现

/**
 * 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 tree2str(TreeNode* root) {
        string string;
        if(root==NULL)
            return string;
        
        string+=to_string(root->val);
        if(root->left||root->right)
        {
            string+='(';
            string+=tree2str(root->left);
            string+=')';
        }
        if(root->right)
        {
            string+='(';
            string+=tree2str(root->right);
            string+=')';
        }
        return string;
    }
};

2.二叉树的层序遍历

1.题目

2.分析原理

题目要求的是把每一层的结点都放在同一个[]里，需要知道那些结点是同一层且第几层，就定义一个levelSize来计数，计算每层存在多少个结点，然后循环放到vector里面，循环次数就是levelSize，循环结束后就把vector的数据放到vector<vector>里面，也就是说levelSize的循环结束就代表一层数据已经取出，还需要再套一层循环在外面，因为要一直更新levelSize的值并一直取结点，直到levelSize的值为0，代表此层没有结点，也就是叶子的下一层了。

3.代码实现

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        int levelSize=0;
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        if(root)
        {
            q.push(root);
            levelSize=1;
        }
        while(levelSize>0)
        {
            vector<int> 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);
            }

            vv.push_back(v);
            levelSize=q.size();
        }
        return vv;


    }
};

题目二

代码实现

只需要加个逆置函数，把vv逆置就可以

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        int levelSize=0;
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        if(root)
        {
            q.push(root);
            levelSize=1;
        }
        while(levelSize>0)
        {
            vector<int> 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);
            }

            vv.push_back(v);
            levelSize=q.size();
        }
        reverse(vv.begin(),vv.end());
        return vv;

    }
};

 

3.二叉树的最近公共祖先

1.题目

2.分析原理

要找到公共祖先，那么俩个结点一定是子孙，也就是会在公共祖先的左右结点处，也可能是在一边，根据例子看，还有特殊情况，就是其中一个结点是祖先。开始前就可以判断是否有结点是祖先，然后构建函数判断是否在左边，而右边函数就可以不用写了，因为不是左就是右，得到两结点的方位值(true为左，false为右)，就可以用来走判断了，如果是一左一右那么就返回这个结点，反着也是，接下来是同左边，就要递归了，因为要用一左一右和其中一个为祖先来找，同右也是，只是用来移动位置来触发一左一右和有一个为祖先的情况。

3.代码实现

/**
 * 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 Inleft(TreeNode* root,TreeNode* x)
    {
        if(root==nullptr)
            return false;
        return root==x
            ||Inleft(root->left,x)
            ||Inleft(root->right,x);
    }
 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q)
            return root;
        bool pIsleft=Inleft(root->left,p);
        bool pIsright=!pIsleft;
        bool qIsleft=Inleft(root->left,q);
        bool qIsright=!qIsleft;

      
        
        if(pIsleft&&qIsright||pIsright&&qIsleft)
            return root;
        else if(pIsleft&&qIsleft)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(pIsright&&qIsright)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        return nullptr;
    }
};

优化

前一个方法的时间复杂度是高的，如果是极端情况”单马尾“就会一直递归，判断方位要递归，移动位置也要递归，那么方位要n次，移动位置也要n次，一共就是O(N^2)了。优化策略就是求出俩个结点到根的路径，就可以转换为两个数组找到相同值交点问题。

如下图，p为6结点，按照前序访问，先把3入栈并判断左右是否有目标结点，有就可以保留，然后是入5并判断，到6就是目标结点保留并返回，而2 7 4是找到目标结点返回就不入栈了。

q为4结点，先入35，然后6入，但是因为没有目标结点在6的左右子数就踢出去，到2，到7，而7也是跟6一样踢出去，就到4了找到并返回。

这样就得到两个路径了，通过找交点就可以找到祖先是哪一个了。

代码实现

 

/**
 * 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* x,stack<TreeNode*>& s)
    {
        if(root==nullptr)
            return false;
        s.push(root);
        if(root==x)
            return true;
        if(GetPath(root->left,x,s))
            return true;
        if(GetPath(root->right,x,s))
            return true;
        s.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath,qPath;
        GetPath(root,p,pPath);
        GetPath(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();
    }
};

4.将二叉树搜索树转换为排序的双向链表

1.题目

2.分析原理

因为要最小元素，就可以用中序遍历，得到有序的数组，返回最前面，遍历过程修改左指针为前驱和右指针为后继指针。定义cur和prev，cur为当前中序遍历到的结点，prev为上一个中序遍历的结点，cur->left,cur->left指向prev，cur->right无法指向中序的下一个，但是可以prev->right指向cur;

个人：总的来说就是双指针思路，一前一后，前后相连，双指针路线就是中序遍历的路线，边走边修改连接方式，最后用循环找到最左结点，并头尾相连完成双链表，返回head。

3.代码实现

/*
// 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 InOrderR(Node* cur,Node* &prev)//要用引用，因为指针本身也是变量，所以会把存储变量传过去，形参是不会指向地址指向的内容的
    {
        if(cur==nullptr)
            return ;
        //下面是左子树部分
        InOrderR(cur->left,prev);
        cur->left=prev;
        if(prev)
            prev->right=cur;
        prev=cur;//更新位置
        //上面就是根节点部分操作
        //下面是右子树部分
        InOrderR(cur->right,prev);
    }
    Node* treeToDoublyList(Node* root) {
        if(root==nullptr)
            return nullptr;
        Node* prev=nullptr;
        InOrderR(root,prev);

        Node* head=root;//这个根节点是二叉树状态时的根，要用循环找到链表的最左边
        while(head->left)
        {
            head=head->left;

        }
       
        head->left=prev;
        prev->right=head;
        return head;
    }
};

5.从前序与中序遍历序列构造二叉树

1.题目

2.分析原理

给出前序遍历的数组和中序遍历的数组来构建二叉树，前序数组可以给出头节点的位置，而中序数组可以根据前序所确定的头节点来分割左右子树的区间，然后用递归来连接结点。首先定义一个变量来作为下标遍历前序数组，这个变量传参要用引用，因为这个值需要记录，在root->left结束后，此时prei就不会找到左子树的根了，因为已经记录完了，剩下就是右子树的根了。还需要begin和end来作为区间表示，用来分割完后把区间传参，在小区间里再次找到根节点，然后又分割区间，直到都返回nullptr为止。

注意：root->left走完后，inbegin和inend已经被改了，不是0了。

3.代码实现

/**
 * 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* Tree(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend)
    {
        if(inbegin>inend)
            return nullptr;
        TreeNode* root=new TreeNode(preorder[prei]);
        int rooti=inbegin;
        while(rooti<inend)
        {
            if(preorder[prei]==inorder[rooti])
            {
                break;
            }
            else
                rooti++;
        }
        prei++;
        root->left=Tree(preorder,inorder,prei,inbegin,rooti-1);//把左子树的根找完剩下就是右子树根，prei是要++才能实现用完找完
        root->right=Tree(preorder,inorder,prei,rooti+1,inend);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i=0;
        return Tree(preorder,inorder,i,0,preorder.size()-1);
    }
};


http://www.kler.cn/a/611393.html

相关文章：

  • SylixOS 中 select 原理及使用分析
  • 计算机三级信息安全技术核心知识点详细定义解析，按章节分类并重点阐述关键概念定义
  • 【加密社】如何创建自己的币圈工具站
  • 解决用户同时登录轮询获取用户信息错乱，使用WebSocket和Server-Sent Events (SSE)
  • 数据可视化TensorboardX和tensorBoard安装及使用
  • MySQL - 数据库基础操作
  • 【每日算法】Day 8-1：广度优先搜索（BFS）算法精讲——层序遍历与最短路径实战（C++实现）
  • 二十五、实战开发 uni-app x 项目（仿京东）- 前后端轮播图
  • 2025最新Chatbox全攻略：一键配置Claude/GPT/DeepSeek等主流模型（亲测可用）
  • # WebSocket 与 Socket.IO 对比与优化
  • RustDesk部署到linux(自建服务器)
  • How to use pgbench to test performance for PostgreSQL?
  • 完全背包模板
  • 突破反爬困境:SDK架构设计，为什么选择独立服务模式（四）
  • 本地部署 LangManus
  • K8S学习之基础五十一：k8s部署jenkins
  • 面试常问系列(二)-神经网络参数初始化之自注意力机制
  • 【hot100】刷题记录(52)-合并K个升序链表
  • How to share files with Linux mint 22 via samba in Windows
  • 【深度破解】爬虫反反爬核心技术实践：验证码识别与指纹伪装