【C++】二叉树进阶OJ题

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

​🌠 作者@阿亮joy.
🎆专栏《吃透西嘎嘎》
🎇 座右铭每个优秀的人都有一段沉默的时光那段时光是付出了很多努力却得不到结果的日子我们把它叫做扎根
在这里插入图片描述

目录

👉根据二叉树创建字符串👈

给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。

空节点使用一对空括号对 “()” 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

在这里插入图片描述

思路本道题就是前序遍历创建字符串创建字符串时需要用括号将左右子树括起来。当左右子树都为空时可以省略掉左右子树的括号。当左子树不为空右子树为空时可以省略掉右子树的括号。当左子树为空右子树不为空时左子树的括号不能省略掉。

class Solution 
{
public:
    string tree2str(TreeNode* root) 
    {
        if(root == nullptr)
            return string();
        
        string str;
        str += to_string(root->val);
        // 左边不为空或者左边为空右边不为空需要加括号
        if(root->left || root->right)
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
		// 右边不为空需要加括号
        if(root->right)
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }

        return str;
    }
};

在这里插入图片描述

以上的解法还可以优化一下因为返回值是string会存在比较多的拷贝构造我们可以通过引用和调用子函数的方式来优化。

class Solution 
{
private:
    void _tree2str(TreeNode* root, string& str)
    {
        if(root == nullptr)
            return;

        str += to_string(root->val);
        if(root->left || root->right)
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }

        if(root->right)
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }
    }
public:
    string tree2str(TreeNode* root) 
    {
        string str;
        _tree2str(root, str);
        return str;
    }
};

在这里插入图片描述

👉二叉树的层序遍历 I 和 II👈

二叉树的层序遍历 I

给你二叉树的根节点 root 返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。

在这里插入图片描述

思路一

  • 首先定义一个队列q和当前层的节点个数levelSize = 0
  • 当根节点root不为空时根节点如队列q且将levelSize设置为 1
  • 当队列不为空时while循环进行。while循环内部用for循环来控制出一层的节点出的同时需要将所出节点的左右孩子也让入队列中如果有的话。
  • 当for结束后队列的size就是下一层的节点个数了。
  • while循环结合后就能够得到二维数组了。

在这里插入图片描述

class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        queue<TreeNode*> q;
        size_t levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }

        vector<vector<int>> vv;
        while(!q.empty())
        {
            vector<int> v;
            // 控制一层一层出
            for(int i = 0; i < levelSize; ++i)
            {
                TreeNode* top = q.front();
                v.push_back(top->val);
                q.pop();

                if(top->left)
                    q.push(top->left);
                if(top->right)
                    q.push(top->right);
            }

            vv.push_back(v);
            // 当前层出完了,下一层的节点都进队列了,队列的size就是下一层的节点个数
            levelSize = q.size();
        }

        return vv;
    }
};

在这里插入图片描述

思路二

  • 先申请一个队列q如果根节点root不为空根节点入队列
  • 然后定义两个TreeNode*变量curend = root和nextend = nullptrcurend为当前层的最后一个节点next是下一层的最后一个节点。
  • 当队列不为空while循环继续。队头所出的节点记为front将front->val尾插到一位数组v中。然后front的左右孩子入队列如果有的话入的同时将nextend更新为最后入队列的节点。
  • 当所出节点front等于当前层最后的节点curend时说明当前层所有节点的值已经收集完毕即可将一维数组v尾插到二维数组vv中。然后还需要做以下操作清空一维数组v准备收集下一层节点的值更新当前层的最后一个节点curend = nextendnext置为空可以不做最好做
  • while循环结束二维数组vv存储的就是层序遍历的结果。
class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        queue<TreeNode*> q;
        if(root)
        {
            q.push(root);
        }

        vector<vector<int>> vv;
        TreeNode* curend = root;    // 当前层最后一个节点
        TreeNode* nextend = nullptr;    // 下一层最后一个节点
        vector<int> v;
        while(!q.empty())
        {
            TreeNode* front = q.front();
            v.push_back(front->val);
            q.pop();

            if(front->left)
            {
                q.push(front->left);
                nextend = front->left;
            }
            if(front->right)
            {
                q.push(front->right);
                nextend = front->right;
            }
            // 当front等于curend时,说明当前层所有节点的值已收集完毕
            // 可以准备收集下一层节点的值
            if(front == curend)
            {
                vv.push_back(v);    
                v.clear();  // 清空一维数组
                curend = nextend;   // 更新curend
            }
        }

        return vv;
    }
};

class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        queue<TreeNode*> q;
        if(root)
        {
            q.push(root);
        }

        vector<vector<int>> vv;
        TreeNode* curend = root;    // 当前层最后一个节点
        TreeNode* nextend = nullptr;    // 下一层最后一个节点
        vector<int> v;
        while(!q.empty())
        {
            TreeNode* front = q.front();
            v.push_back(front->val);
            q.pop();

            // 只要是下一层节点入了队列,就需要更新nextend为入队列的节点
            if(front->left)
            {
                q.push(front->left);
                nextend = front->left;
            }
            if(front->right)
            {
                q.push(front->right);
                nextend = front->right;
            }
            // 当front等于curend时,说明当前层所有节点的值已收集完毕
            // 可以准备收集下一层节点的值
            if(front == curend)
            {
                vv.push_back(v);    
                v.clear();  // 清空一维数组
                curend = nextend;   // 更新curend
            }
        }

        return vv;
    }
};

在这里插入图片描述
注以上两种方法还有用来求二叉树的最大宽度。

其实还有一种思路双队列也可以解决这道题。一个队列存储节点另一个队列存节点的所在层数大家可以尝试一下。

在这里插入图片描述

二叉树的层序遍历 II

给你二叉树的根节点 root 返回其节点值自底向上的层序遍历。即按从叶子节点所在层到根节点所在的层逐层从左向右遍历

在这里插入图片描述

我们只需要将二叉树的层序遍历 I 中得到的二维数组vv反转一下就能够解决这道题了。

class Solution 
{
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        queue<TreeNode*> q;
        size_t levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }

        vector<vector<int>> vv;
        while(!q.empty())
        {
            vector<int> v;
            // 控制一层一层出
            for(int i = 0; i < levelSize; ++i)
            {
                TreeNode* top = q.front();
                v.push_back(top->val);
                q.pop();

                if(top->left)
                    q.push(top->left);
                if(top->right)
                    q.push(top->right);
            }

            vv.push_back(v);
            // 当前层出完了,下一层的节点都入队列了,队列的size就是下一层节点的个数
            levelSize = q.size();
        }

        reverse(vv.begin(), vv.end());
        return vv;
    }
};

在这里插入图片描述

👉二叉树的最近公共祖先👈

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”

在这里插入图片描述
在这里插入图片描述

思路一

在这里插入图片描述

class Solution 
{
private:
    // 查找节点x是否在以sub为根节点的树中
    bool Find(TreeNode* sub, TreeNode* x)
    {
        if(sub == nullptr)
            return false;
        
        return sub == x
            || Find(sub->left, x)
            || Find(sub->right, x);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root == nullptr)
            return nullptr;
        
        // 其中一个节点为根节点,则最近公共祖先为根节点
        if(root == p || root == q)
            return root;

        // p、q在根节点的左右子树中
        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;
        qInLeft = Find(root->left, q);
        qInRight = !qInLeft;

        if(pInLeft && qInLeft)  // p、q都在根节点的左子树中,转化成子问题
            return lowestCommonAncestor(root->left, p, q);
        else if(pInRight && qInRight)   // p、q都在根节点的右子树中,转化成子问题
            return lowestCommonAncestor(root->right, p, q);
        else    // p、q一个在左,另一个在右最近公共祖先为根节点
            return root;
    }
};

在这里插入图片描述

注因为 p 和 q 一定在树中所以 p 在左子树那么它一定不会在右子树中q 同理。这种解法的时间复杂度为O(h*N)h为树的高度N为节点的个数。

思路二
这种思路是求出从根节点root到p和q的路径路径用栈来存储。因为路径长短不一样所以先让长的弹出长度差个节点然后两个栈一起弹出节点直至栈顶节点相同那么栈顶节点就是p和q的最近公共祖先。这种解法的思路类似于链表相交的思路时间复杂度为O(N)。

在这里插入图片描述

class Solution 
{
private:
    bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if(root == nullptr)
            return false;

        path.push(root);
        if(root == x)   // 根节点就是p、q
            return true;
        if(FindPath(root->left, x, path))   // p、q在root的左子树中
            return true;
        if(FindPath(root->right, x, path))  // p、q在root的右子树中
            return true;
        
        path.pop();     // 经过root无法到达p、q,所以要将root弹出
        return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        stack<TreeNode*> pPath, qPath;
        FindPath(root, p, pPath);   // pPath中储存的是root到p的路径
        FindPath(root, q, qPath);   // qPath中储存的是root到q的路径

        // 路径长的弹出长度差个节点
        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();
    }
};

在这里插入图片描述

思路三

思路三是思路一的精简版本时间复杂度为O(N)。

在这里插入图片描述

class Solution 
{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        // root为空或者是p、q中的一样都要返回自己
        if(root == nullptr || root == p || root == q)
            return root;
        
        TreeNode* InLeft = lowestCommonAncestor(root->left, p, q);
        TreeNode* InRight = lowestCommonAncestor(root->right, p, q);

        // InLeft和InRight都不为空,则根节点为最近公共祖先
        if(InLeft && InRight)
            return root;
        
        // InLeft和InRight谁不为空,谁就是最近公共祖先
        return InLeft ? InLeft : InRight;
    }
};

在这里插入图片描述

👉二叉搜索树与双向链表👈

输入一棵二叉搜索树将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点只能调整树中节点指针的指向。

链表中的每个节点都有一个前驱和后继指针。对于双向循环链表第一个节点的前驱是最后一个节点最后一个节点的后继是第一个节点。

当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

在这里插入图片描述
在这里插入图片描述

思路本道题要求左指针 left 指向中序的前一个节点右指针 right 指向中序的后一个节点。我们可以采用prev来记录当前节点cur的前一个节点那么prev->right = cur, cur->left = prev这样就可以将二叉搜索树转化成双向链表了。注意prev是Node*的引用这样才能链接起来。

class Solution 
{
private:
    void InordertreeToDoublyList(Node* cur, Node*& prev)
    {
        if(cur == nullptr)
            return;
        
        InordertreeToDoublyList(cur->left, prev);
        cur->left = prev;
        if(prev != nullptr)
            prev->right = cur;
        prev = cur;
        InordertreeToDoublyList(cur->right, prev);
    }
public:
    Node* treeToDoublyList(Node* root) 
    {
    	// 根节点为空,直接返回nullptr即可
        if(root == nullptr)
            return nullptr;
        
        Node* prev = nullptr;
        InordertreeToDoublyList(root, prev);
        // 找到中序第一个节点
        Node* first = root;
        while(first->left)
        {
            first = first->left;
        }
        // 找到中序最后一个节点
        Node* last = root;
        while(last->right)
        {
            last = last->right;
        }
        // 第一个节点与最后一个节点链接起来形成双向循环链表
        first->left = last;
        last->right = first;

        return first;
    }
};

在这里插入图片描述

👉从前序与中序遍历序列构造二叉树👈

给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。

在这里插入图片描述
在这里插入图片描述

思路前序结果创建树中序分割左右子树。子树区间确认是否继续递归创建子树区间不存在则是空树。

class Solution 
{
private:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& preI, int inBegin, int inEnd)
    {
        if(inBegin > inEnd)
            return nullptr;
        
        // 构建根
        TreeNode* root = new TreeNode(preorder[preI]);
        // 用中序结果来分割左右子树
        int inI = inBegin;
        while(inI <= inEnd)
        {
            if(inorder[inI] == root->val)
                break;
            else
                ++inI;
        }

        // [inBegin, inI - 1] inI [inI + 1, inEnd]
        // 先构建左子树再构建右子树
        ++preI;    // 找出左右子树的根
        root->left = _buildTree(preorder, inorder, preI, inBegin, inI - 1);
        root->right = _buildTree(preorder, inorder, preI, inI + 1, inEnd);
        
        return root;
    }
public:


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

在这里插入图片描述
注因为preI是遍历前序数组preinorde的下标整个递归遍历中都要使用所以需要传引用。如果不是传引用而是传值的话左子树构建好返回。因为preI不是引用只是形参无法将上一次递归的结果保留下来那么这样就无法找到右子树的根了也就无构建右子树了。

👉从后序与中序遍历序列构造二叉树👈

给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。

在这里插入图片描述
在这里插入图片描述

思路后序结果创建树中序分割左右子树。子树区间确认是否继续递归创建子树区间不存在则是空树。因为后序遍历序列是左子树、右子树、根所以后序遍历序列的最后一个元素是根节点位于它前面的是右子树的根节点。所以先要构建右子树再来构建左子树。最后把根和左右子树链接在一起二叉树就构建完成了。

class Solution 
{
private:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posI, int inBegin, int inEnd)
    {
        if(inBegin > inEnd)
            return nullptr;
        
        TreeNode* root = new TreeNode(postorder[posI]);
        // 中序分割左右子树
        int inI = inBegin;
        while(inI <= inEnd)
        {
            if(inorder[inI] == root->val)
                break;
            else
                ++inI;
        }

        // 先构建右子树再构建左子树
        // [inBegin, inI - 1] inI [inI + 1, inEnd]
        --posI;
        root->right = _buildTree(inorder, postorder, posI, inI + 1, inEnd);;
        root->left = _buildTree(inorder, postorder, posI, inBegin, inI - 1);

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

在这里插入图片描述
注中序与后序遍历序列是无法确定唯一的一块树的使用两个遍历结果确定树的结构 其中有一个遍历结果必须要是中序遍历结果。

👉总结👈

本篇博客主要讲解了二叉树进阶的 OJ 题每道题都是非常经典的面试题。那么以上就是本篇博客的全部内容了如果大家觉得有收获的话可以点个三连支持一下谢谢大家💖💝❣️

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：狗厂的N+1+2毕业，我觉得还是挺良心的

下一篇：springboot2.3.x版本发生异常时，响应的message和exception为空问题

“【C++】二叉树进阶OJ题” 的相关文章

【C++】面向对象---继承(万字详解)1年前 (2023-02-02)
P1019题解 单词接龙（c++）1年前 (2023-02-02)
101、【树与二叉树】leetcode ——617. 合并二叉树：递归法+迭代法（C++版本）1年前 (2023-02-02)
C++跨平台（支持LINUX，WIN32，Solaris，MacOS，FreeBSD）的网络通信库及服务器编程框架源码1年前 (2023-02-02)
【C/C++无聊练手（四）】用C++模板写一个带迭代器的树状数组，用于求前缀和1年前 (2023-02-02)
C++静态成员和静态函数（非类）1年前 (2023-02-02)
C++：C++全局变量：看完还不懂全局变量来捶我1年前 (2023-02-02)
C++初学者学习笔记1年前 (2023-02-02)
【C++】多态1年前 (2023-02-02)
C++关于初始化列表的细节（必须/不能使用初始化列表的情况、初始化列表的效率分析）1年前 (2023-02-02)

阿里云国际版