【C++】二叉搜索树经典OJ题目

这篇具有很好参考价值的文章主要介绍了【C++】二叉搜索树经典OJ题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

根据二叉树创建字符串

【C++】二叉搜索树经典OJ题目

解题思路

这道题是让我们使用前序遍历的方式来创建字符串,但是有一点需要注意的是,再创建的字符串中,需要将每一个左右子树用括号括起来。这里扩括号的时候有两点需要注意的细节:

  • 当左右子树都为空时,该节点左右子树的括号都可以省略掉。
  • 当左子树不为空,右子树为空时,省略掉右子树的括号。
  • 当左子树为空,右子树不为空时,左子树的括号不能省略掉。

代码实现

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root == nullptr)
            return "";
        string 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;
    }
};

【C++】二叉搜索树经典OJ题目


二叉树的层序遍历

【C++】二叉搜索树经典OJ题目

解题思路

首先,定义一个队列q、记录当前层节点个数的变量levelnum vector <vector < int > >来存储遍历后的结果。 然后判断根节点是不是空, 如果不是空先将根节点入队列,然后levelnum置为1。

外层循环控制队列是否为空,如果为空,则说明节点已经全部出队。该树也已经被访问完了。内层循环来控制每一层节点的个数,然后在队列中按照对头——对尾的顺序依次访问队列中的每一个节点,每访问一个节点,就让该节点出队,并让该节点的左右非空孩子节点入队,这样一来,上一层的节点全部出队后,下一层的节点也就全部入队了。内层循环每循环完一次,就将新队列中的元素个数赋给levelnum 。这样每一层的节点就被依次插入二维数组中的每一行中了。

代码实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        int levelnum = 0;
        if(root){
            q.push(root);
            levelnum = 1;
        }
        while(!q.empty())
        {
            vector<int> v;
            while(levelnum--)
            {
                TreeNode* tmp = q.front();
                v.push_back(tmp->val);
                q.pop();
                if(tmp->left)
                    q.push(tmp->left);
                if(tmp->right)
                    q.push(tmp->right);
            }
            vv.push_back(v);
            levelnum = q.size();
        }
        return vv;
    }
};

【C++】二叉搜索树经典OJ题目


二叉树的层序遍历II

【C++】二叉搜索树经典OJ题目

解题思路

这道题目和上一道题的不同点在于:上一道题目是从上到下依次遍历每一层的元素,这道题是从下到上依次遍历每一层。所以对于这道题目,我们只需要将上一道题目的代码拷贝过来,然后将结果逆置一下就可以了。

代码实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        int levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }
        while(!q.empty())
        {
            vector<int> v;
            while(levelSize--)
            {
                TreeNode* tmp = q.front();
                v.push_back(tmp->val);
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
                q.pop();

            }
            vv.push_back(v);
            levelSize = q.size();
        }
        return vv;
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> vv = levelOrder(root);
        reverse(vv.begin(),vv.end());
        return vv;
    }
};

【C++】二叉搜索树经典OJ题目


二叉树的最近公共祖先

【C++】二叉搜索树经典OJ题目

解题思路

先定义两个栈,用来存储从根节点到p从根节点到q的路径,将他们的路径中的每一个节点存储到栈中。我们需要找的就是这两条路径中相同的那个节点。也就是我们需要先控制栈中的元素个数相同,然后再比较栈顶的元素是否相同,如果不相同则同时弹出两个栈中栈顶的元素,直到两个栈中栈顶的元素相同,此时栈顶的元素就是我们要找的公共祖先。

代码实现

class Solution {
public:
    //定义两个栈,找到两个节点的路径,压入栈中
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        //节点为空,直接返回false
        if(root == nullptr)
            return false;
        //节点不为空
        path.push(root);
        if(root == x)
            return true;
        if(GetPath(root->left,x,path))
            return true;
        if(GetPath(root->right,x,path))
            return true;
        path.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();
    }
};

【C++】二叉搜索树经典OJ题目


二叉搜索树与双向链表

【C++】二叉搜索树经典OJ题目

解题思路

当前节点的指针用cur表示,再定义一个prev指针,让prev来表示当前节点cur的前一个结点,这样通过不断递归的方式访问每一个节点之后就可以将二叉树转换成双向循环链表了。这里我们需要注意的是,prev一定要使用引用传参,因为每一层节点的prev都是上一次函数调用的cur。

代码实现

class Solution {
public:
    void InOrderConvert(Node* cur, Node* &prev)
	{
		if(cur == nullptr)
			return;
		InOrderConvert(cur->left, prev);
		cur->left = prev;
		if(prev)
			prev->right = cur;
		prev = cur;
		InOrderConvert(cur->right, prev);
	}
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return nullptr;
        Node* prev = nullptr;
		InOrderConvert(root, prev);

		Node* cur = root;
		while(cur && cur->left)
		{
			cur = cur->left;
		}
        Node* Rcur = root;
        while(Rcur && Rcur->right)
        {
            Rcur = Rcur->right;
        }
        cur->left = Rcur;
        Rcur->right = cur;
		return cur;
    }
};

【C++】二叉搜索树经典OJ题目


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

【C++】二叉搜索树经典OJ题目

解题思路

大思路很简单,但是这道题目写起来却不是很容易,通过前序我们可以找到根节点,中序分割出左右子树,如果区间还存在说明还有节点未构建完,如果区间不存在说明已经没有节点可以构建,直接返回空。

代码实现

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int begin,int end) 
    {
        if(begin > end)
            return nullptr;
        //创建根节点
        TreeNode* newnode = new TreeNode(preorder[prei]);
        
        //分割左右子区间
        int rooti = begin;
        while(rooti <= end)
        {
            if(inorder[rooti] == preorder[prei])
                break;
            else 
                rooti++;
        }
        prei++;
        //递归创建左右子树
        newnode->left = _buildTree(preorder, inorder, prei, begin, rooti - 1);
        newnode->right = _buildTree(preorder, inorder, prei, rooti + 1, end);
        return newnode;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

【C++】二叉搜索树经典OJ题目


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

【C++】二叉搜索树经典OJ题目

解题思路

因为后续序列和前序序列有一点点不同,所以这里我们必须从后往前依次访问后序序列中的每一个元素,这样才能找出每一棵子树的根节点并从中序将左右子区间分割开。这里和前序不一样的是,这里我们需要先构建右子树,在构建左子树,最后将根节点和左右子树链接起来。

代码实现

class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int &pos, int begin, int end)
    {
        if(begin > end)
            return nullptr;
        TreeNode* newnode = new TreeNode(postorder[pos]);
        int rooti = begin;
        while(rooti <= end)
        {
            if(postorder[pos] == inorder[rooti])
                break;
            else
                rooti++;
        }
        pos--;
        //分割左右子区间

        newnode->right = _buildTree(inorder, postorder, pos, rooti + 1, end);
        newnode->left = _buildTree(inorder, postorder, pos, begin, rooti - 1);
        return newnode;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size() - 1;
        return _buildTree(inorder, postorder, i, 0, postorder.size() - 1);
    }
};

【C++】二叉搜索树经典OJ题目


二叉树的前序遍历(非递归)

【C++】二叉搜索树经典OJ题目

解题思路

前序遍历的顺序是根、左子树、右子树。因此最后我们遍历整棵树的时候,一定是先访问左路节点,然后访问左路节点的右子树,左路节点的右子树又可以看作一棵二叉树、然后继续二叉子树的前序遍历,最后直到遍历访问整棵二叉树。

我们需要定义一个栈st、一个vector v 和一个 TreeNode* curcur初始化为root。定义一个while循环,循环结束的条件是cur不为空,或者st不为空,首相我们先将左路节点依次插入栈中,同时也将左路节点插入到vector中,这时左路节点就已经访问完了,然后将栈顶元素保存下来并出栈,并将cur指向栈顶元素的右子树,做像上面一样的操作。这样就能保证每棵子树都能够按照根——左子树——右子树的顺序访问每一个节点,最后遍历整棵树就能达到预期的结果。

代码实现

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> v;
        stack<TreeNode*> st;
        while(cur || !st.empty())
        {
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            //访问每个根节点的右子树
            TreeNode* tmp = st.top();
            st.pop();
            cur = tmp->right;
        }
        return v;
    }
};

【C++】二叉搜索树经典OJ题目


二叉树的中序遍历(非递归)

【C++】二叉搜索树经典OJ题目

解题思路

中序遍历的思路和前序遍历的思路也差不多,有一点不同的就是中序遍历的顺序是左子树——根——右子树,和前序遍历一样,先将根节点入栈,不同的是入栈的同时不能访问节点,等到左路节点全部入栈后,先将该节点保存,然后访问该节点并将该节点弹出栈,然后将cur指向该节点的右子树。然后while循环中重复和前序遍历一样的操作。

代码实现

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* tmp = st.top();
            v.push_back(tmp->val);
            st.pop();
            cur = tmp->right;
        }
        return v;
    }
};

【C++】二叉搜索树经典OJ题目


二叉树的后序遍历(非递归)

【C++】二叉搜索树经典OJ题目

解题思路

后序遍历的顺序是左子树——右子树——根,所以我们在访问根节点的时候必须保证左子树和右子树都已经被访问过了才行。同样,和上面的思路一样,我们同样是先将左路节点入栈并且不访问,当左路节点全部入栈后。取栈顶元素,这时我们需要先判断该节点是否有右子树,或者该节点的右子树是否被访问过。判断该节点的右子树是否被访问过的方法是:设置一个指针 prev 来记录前一个访问过的节点,因为只有右子树访问完才能访问根节点,所以我们只需要判断该节点的右子树是否是上一个访问过的节点就可以了。 同时,如果右子树为空也能直接访问该节点。

代码实现

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* tmp = st.top();
            if(tmp->right == nullptr || prev == tmp->right)
            {
                st.pop();
                v.push_back(tmp->val);
                prev = tmp;
            }
            else
            {
                cur = tmp->right;
            }
        }
        return v;
    }
};

【C++】二叉搜索树经典OJ题目文章来源地址https://www.toymoban.com/news/detail-446694.html


到了这里,关于【C++】二叉搜索树经典OJ题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++力扣题目700--二叉搜索树中的搜索

    给定二叉搜索树(BST)的根节点  root  和一个整数值  val 。 你需要在 BST 中找到节点值等于  val  的节点。 返回以该节点为根的子树。 如果节点不存在,则返回  null  。 示例 1: 示例 2:   之前我们讲的都是普通二叉树,那么接下来看看二叉搜索树。 在关于二叉树,你该了

    2024年01月17日
    浏览(53)
  • C++力扣题目450--删除二叉搜索树中的节点

    给定一个二叉搜索树的根节点  root  和一个值  key ,删除二叉搜索树中的  key  对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到需要删除的节点; 如果找到了,删除它。 示例

    2024年01月17日
    浏览(36)
  • C++力扣题目530--二叉搜索树的最小绝对值

    给你一个二叉搜索树的根节点  root  ,返回  树中任意两不同节点值之间的最小差值  。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: 示例 2: 树中节点的数目范围是  [2, 104] 0 = Node.val = 105 题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。 注意

    2024年02月02日
    浏览(45)
  • 多种方法解决leetcode经典题目-LCR 155. 将二叉搜索树转化为排序的双向链表, 同时弄透引用变更带来的bug

    这段代码实际上是一个常见的算法题目的解法,目标是将一个二叉搜索树转换为一个排序的双向链表。整个过程是通过中序遍历来实现的,遍历过程中修改节点的左右指针来构建双向链表。代码中使用了一个额外的节点 dummy 来帮助构建双向链表,并使用 pre 节点来保存前一个

    2024年02月06日
    浏览(43)
  • 链表经典算法OJ题目

    直接在原链表里删除val元素,然后让val前一个结点和后一个节点连接起来。 这时我们就需要3个指针来遍历链表: pcur  —— 判断节点的val值是否于给定删除的val值相等 prev ——保存pcur的前一个节点,为删除节点后,连接pcur之后的节点做准备 del —— 保存pcur之后的一个节点

    2024年04月26日
    浏览(33)
  • 二叉树基础oj题目

    前文中,介绍了二叉树的基本概念及基础操作,进一步对于二叉树的递归遍历及子问题的处理思想有了一定的了解。本文将带来几道二叉树经典的oj题目。 对称二叉树 平衡二叉树 二叉树的层序遍历 leetcode题目链接 题目描述:给你一个二叉树的根节点 root , 检查它是否轴对称

    2024年01月21日
    浏览(42)
  • 二叉树OJ题目合集(单值、对称、平衡、构建加遍历)

    目录 前言: 一:单值二叉树 二:二叉树遍历 核心点 (1)前序 (2)中序 (3)后序 三:判断两颗树是否相同 四:判断二叉树是否对称 五:判断一颗树是否为另一颗树的子树 六:平衡二叉树 七:二叉树的构建加遍历 这一部分适合已经 适用于已经掌握二叉树基础的同学(遍历,求节

    2024年02月02日
    浏览(37)
  • 【数据结构】二叉树的相关操作以及OJ题目

    当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点的左子树、根节点的右子树组成的。 从概念中可以看出,二叉树定义是递归式的,因

    2024年03月19日
    浏览(48)
  • 二叉树经典OJ题——【数据结构】

    W...Y的主页  😊 代码仓库分享 💕  今天我们来进行二叉树的OJ练习,就是利用二叉树的前序、中序、后续以及晨序遍历的特性进行OJ训练。话不多说,来看我们的第一道题。 【leetcode 965.单值二叉树】 OJ链接  如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二

    2024年02月07日
    浏览(44)
  • 二叉树经典算法题目

    省略 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7] , 返回它的最大深度 3 。 思路:递归,当前数的深度等于左子数和右子树其中最大深

    2024年02月09日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包