二叉树题目合集(C++)

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

1.二叉树创建字符串(简单)

链接:二叉树创建字符串

题目要求:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

PS:题目描述的不是特别清楚,其实就是前序遍历树,然后用括号分别包含左子树和右子树遍历结果

基础思路:
(1)不考虑括号去重的话,其实只要访问完当前节点后递归访问左右子树即可,并且在访问前加左括号,访问完毕后加右括号,当前节点为空时返回即可。代码如下:

class Solution {
public:
    string ret;
    string tree2str(TreeNode* root) {
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root)
    {
        if(root == nullptr)  return;
        ret += to_string(root->val);
        ret += '(', dfs(root->left), ret += ')';
        ret += '(', dfs(root->right), ret += ')';
    }
};

二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构


(2) 对于括号去重,主要围绕左右子树为空,我们需要分情况讨论:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构


代码:文章来源地址https://www.toymoban.com/news/detail-734071.html

class Solution {
public:
    string ret;
    string tree2str(TreeNode* root) {
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root)
    {
        if(root == nullptr)  return;
        ret += to_string(root->val);
        if(root->left || root->right)  ret += '(', dfs(root->left), ret += ')';
        if(root->right)  ret += '(', dfs(root->right), ret += ')';
    }
};



2.二叉树的分层遍历(中等)

链接:二叉树的分层遍历

题目要求:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构


基础思路:
(1) 二叉树层序遍历的思想其实很简单,就是借助队列,父节点带出子节点,依靠队列先进先出的特点控制访问顺序
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

(2) 这个题目的关键点在于如何得知当前层和下一层的节点数,因为我们需要每一层都构建一个数组来存储结果。这里采用的解决方案是用一个next变量记录下一层的节点数,count(count初始为1)记录当前层的节点数,当前层访问完把next赋给count即可。


代码:

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root == nullptr)  return ret;
        queue<TreeNode*> q;
        q.push(root);
        int count = 1;  //每一层的节点数
        while(!q.empty())
        {
            vector<int> tmp;
            int next = 0;  //用一个变量记录下一层的节点
            for(int i = 0; i < count; i++)
            {
                TreeNode* node = q.front();
                q.pop();
                tmp.push_back(node->val);      
                if(node->left)  q.push(node->left), next++;   
                if(node->right)  q.push(node->right), next++;           
            }
            count = next;
            ret.push_back(tmp);
        }
        return ret;
    }
};



3.二叉树的最近公共祖先(中等)

链接:二叉树的最近公共祖先
题目要求:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

  1. 解法一(时间复杂度高):
    基础思路:
    二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

解法一代码:

//理想是N*logN,对于退化成链表的情况变成O(N ^ N)
class Solution {
public:
    bool isTree(TreeNode* root, TreeNode* x)
    {
        if(root == nullptr)  return false;
        if(root->val == x->val)  return true;
        return isTree(root->left, x) || isTree(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q)  return root;
        bool pInLeft = isTree(root->left, p);
        bool pInRight = !pInLeft;  //不在左树就在右树
        bool qInLeft = isTree(root->left, q);
        bool qInRight = !qInLeft;
        if((pInLeft && qInRight) || (pInRight && qInLeft))  //p,q分别在左右子树
            return root;
        if(pInLeft && qInLeft)  return lowestCommonAncestor(root->left, p, q); //pq都在左树
        else  return lowestCommonAncestor(root->right, p, q);  //pq都在右树
    }
};

  1. 解法二(时间复杂度低):
    基础思路:
    第二种思路也不是很难,将根到p,q节点的路径找出来从后向前找相交的节点即可,这样不好理解,还是看图:
    二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

解法二代码:

//找路径,转换为链表交点,用栈来存储路径,O(N)
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(); 
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        stack<TreeNode*> path1;
        stack<TreeNode*> path2;
        FindPath(root, p, path1);
        FindPath(root, q, path2);
        while(path1.size() != path2.size())  //长路径先走
        {
            if(path1.size() > path2.size())  path1.pop();
            else  path2.pop();
        }
        while(path1.top() != path2.top())
        {
            path1.pop(), path2.pop();
        }
        return path1.top();  //随便返回一个即可
    }
};



4.二叉树搜索树转换成排序双向链表(中等)

链接:二叉树搜索树转换成排序双向链表

题目要求:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

基础思路:
(1)因为是搜索树,我们采用类似中序遍历的方式解题。
(2)这个题的关键在于找前置节点,只要找到当前节点的前置就可以进行链接。

具体过程如下:

  1. 两个指针,prev记录前置,cur记录当前,prev初始为空
  2. cur为空,返回。
  3. (1)cur非空,先递归走左;
    (2)左走完后prev就是前置,链接:cur->left = prev,prev->right = cur(这里prev非空)。
    (3)链接完毕后更新前置,prev = cur
    (4)左走完,递归右,链接右子树。
  4. 最后需要确定链表头节点,这个可以
    ①转换前找:树的最左下角的节点
    ②转换后找:从原根部节点一直向左即可。

先一路递归向左走到空
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

代码:

class Solution {
public:
	void _Convert_order(TreeNode* cur, TreeNode*& prev)
	{
		if(cur == nullptr)  return;
		_Convert_order(cur->left, prev);
		cur->left = prev;
		if(prev)  prev->right = cur;
		prev = cur;
		_Convert_order(cur->right, prev);
	}
	
    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
        TreeNode* cur = pRootOfTree, *prev = nullptr;
		_Convert_order(cur, prev);
		TreeNode* ret = pRootOfTree;
		while(ret && ret->left)  //(1)有空树的情况(2)先链接好再向左找目标节点即可
		{
			ret = ret->left;
		}
		return ret;
    }
};



5.根据树的前序遍历与中序遍历构造二叉树(中等)

链接:构造二叉树

题目要求:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构

基础思路:
(1)前序定根,中序定左右
(2)先构造根,然后找到当前节点在中序数组的位置,把左右子树的节点划分出来。
(3)依据划分出的中序区间递归走左和右,区间不存在说明这个位置为空,返回空。
左右走完后链接起来即可。左右链接好了返回该树的根部节点

处理细节:
(1)怎么找到当前节点在中序数组的位置:
①一种方式是遍历中序区间,这样每一层都需要遍历,时间复杂度高
②一种是用哈希表进行存储,用值映射中序下标,时间复杂度低。
本文选择方式②。

前序遍历的过程走一下这个过程:
二叉树题目合集(C++),算法,深度优先,算法,笔记,力扣,数据结构


代码:

class Solution {
public:
    unordered_map<int, int> ord;
    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 rooti = ord[preorder[prei++]];
        //划分出三段区间:[inbegin, rooti - 1] rooti [rooti + 1, inend]
        root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);
        root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++)
        {
            ord[inorder[i]] = i;
        }
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

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

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

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

相关文章

  • 求二叉树的最小深度(深度优先和广度优先)

    自己建一个二叉树,然后分别使用深度优先和广度优先找到二叉树的最小深度。 代码中有注释哦~

    2024年02月12日
    浏览(43)
  • 【完全二叉树节点数!】【深度优先】【广度优先】Leetcode 222 完全二叉树的节点个数

    ---------------🎈🎈题目链接🎈🎈------------------- 完全二叉树只有两种情况: 情况一:就是满二叉树, 情况二:最后一层叶子节点没有满。 对于情况一,可以直接用 2 ^ 树深度 - 1 来计算,注意这里根节点深度为1。 对于情况二,分别递归左孩子,和右孩子,递归到某一深度一

    2024年02月19日
    浏览(35)
  • 二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)

    目录 一、树概念及结构(了解)  1.1树的概念  1.2树的表示  二、二叉树概念及结构  2.1概念  2.2现实中的二叉树: 2.3数据结构中的二叉树: 2.4特殊的二叉树:  2.5 二叉树的存储结构  2.51 顺序存储:  2.5.2 链式存储: 三、二叉树性质相关选择题练习  四、二叉树的实现 4

    2024年02月03日
    浏览(45)
  • 【二叉树复习】C++ 二叉树复习及题目解析 (1)

    目录 二叉树 树 相关概念 树的表示 二叉树 概念 存储结构 小练习 树题目: leetcode 965 单值二叉树。 leetcode 103. 二叉树的最大深度 leetcode 226 翻转二叉树 leetcode100 相同的树 leetcode 101 对称二叉树 leetcode 144前序遍历 94 中序遍历 145 后序遍历 leetcode 572 另一棵树的子树 本文将从二

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

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

    2024年02月09日
    浏览(58)
  • ※【回溯】【深度优先前序】Leetcode 257. 二叉树的所有路径

    ---------------🎈🎈257. 二叉树的所有路径 题目链接🎈🎈------------------- 时间复杂度O(N) 空间复杂度O(N) 深度优先遍历 添加了 StringBulider 替代字符串拼接提升效率 toString() 转化为String .append() 添加元素 时间复杂度O(N) 空间复杂度O(N)

    2024年02月20日
    浏览(37)
  • C++力扣题目617--合并二叉树

    给你两棵二叉树:  root1  和  root2  。 想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则

    2024年01月20日
    浏览(42)
  • C++力扣题目654--最大二叉树

    给定一个不重复的整数数组  nums  。  最大二叉树  可以用下面的算法从  nums  递归地构建: 创建一个根节点,其值为  nums  中的最大值。 递归地在最大值  左边  的  子数组前缀上  构建左子树。 递归地在最大值  右边  的  子数组后缀上  构建右子树。 返回  nums  构

    2024年01月20日
    浏览(40)
  • C++力扣题目101--对称二叉树

    力扣题目链接(opens new window) 给定一个二叉树,检查它是否是镜像对称的。   首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了 其实我们要比较

    2024年01月25日
    浏览(38)
  • 【算法练习】leetcode算法题合集之二叉树篇

    前序遍历,中序遍历,后序遍历是根据处理根节点的位置来命名的。 树的处理大多用到了递归,递归需要知道终止条件。 前序遍历(中左右) 144.二叉树的前序遍历 中左右,先处理根节点,再处理左子树,再处理右子树 非递归版实现前序遍历 使用栈,当前节点处理完,先塞

    2024年02月01日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包