二叉树题目合集（C++）

news/2024/7/20 20:44:18 标签: 深度优先, 算法, 笔记, 力扣, 数据结构

二叉树题目合集

    • 1.二叉树创建字符串（简单）
    • 2.二叉树的分层遍历（中等）
    • 3.二叉树的最近公共祖先（中等）
    • 4.二叉树搜索树转换成排序双向链表（中等）
    • 5.根据树的前序遍历与中序遍历构造二叉树（中等）

1.二叉树创建字符串（简单）

链接：二叉树创建字符串

题目要求：
在这里插入图片描述

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 += ')';
    }
};

在这里插入图片描述


（2） 对于括号去重，主要围绕左右子树为空，我们需要分情况讨论：
在这里插入图片描述


代码：

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.二叉树的分层遍历（中等）

链接：二叉树的分层遍历

题目要求：
在这里插入图片描述


基础思路：
（1） 二叉树层序遍历的思想其实很简单，就是借助队列，父节点带出子节点，依靠队列先进先出的特点控制访问顺序。
在这里插入图片描述

（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.二叉树的最近公共祖先（中等）

链接：二叉树的最近公共祖先
题目要求：
在这里插入图片描述

  1. 解法一(时间复杂度高)：
    基础思路：
    在这里插入图片描述

解法一代码：

//理想是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节点的路径找出来，从后向前找相交的节点即可，这样不好理解，还是看图：
    在这里插入图片描述

解法二代码：

//找路径，转换为链表交点，用栈来存储路径，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.二叉树搜索树转换成排序双向链表（中等）

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

题目要求：
在这里插入图片描述

基础思路：
（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. 最后需要确定链表头节点，这个可以
    ①转换前找：树的最左下角的节点。
    ②转换后找：从原根部节点一直向左即可。

先一路递归向左走到空：
在这里插入图片描述

代码：

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.根据树的前序遍历与中序遍历构造二叉树（中等）

链接：构造二叉树

题目要求：
在这里插入图片描述

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

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

按前序遍历的过程走一下这个过程：
在这里插入图片描述


代码：

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);
    }
};

http://www.niftyadmin.cn/n/5133636.html

相关文章

uniapp 常见的问题以及解决办法

uniapp 常见的问题以及解决办法

当开发UniApp时&#xff0c;可能会遇到一些常见问题。以下是一些常见问题及其解决办法&#xff1a; 1. 页面或组件无法正常显示 确保页面或组件的路径和文件名的大小写正确。检查模板代码中是否存在错误或不完整的标签闭合。使用调试工具&#xff08;如Chrome开发者工具&…
阅读更多...
简单方法搭建个人网站

简单方法搭建个人网站

随着互联网的发展&#xff0c;越来越多的人希望拥有一个属于自己的网站&#xff0c;用来展示自己的个人才华、推广自己的产品或服务。但是&#xff0c;很多人都因为没有编程知识而望而却步。现在&#xff0c;有一个简单的方法可以帮助你轻松搭建网站&#xff0c;无需编程知识。…
阅读更多...
【每日一题Day362】LC274H 指数 | 二分答案

【每日一题Day362】LC274H 指数 | 二分答案

H 指数【LC274】 给你一个整数数组 citations &#xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义&#xff1a;h 代表“高引用次数” &#xff0c;一名科研人员的 h 指数 是指他&#xff08;她&a…
阅读更多...
【计算机网络】路由器的工作原理

【计算机网络】路由器的工作原理

文章目录 输入端口处理和基于目的地转发交换结构输出端口处理排队问题参考资料 路由器的四个组件 输入端口(input port)&#xff1a;执行物理层功能&#xff08;input port 左边方框、output port 右边方框&#xff09;、数据链路层功能&#xff08;input/output port 中间方框…
阅读更多...
Godot 官方2D C#重构(4)：TileMap进阶使用

Godot 官方2D C#重构(4)：TileMap进阶使用

文章目录 前言完成内容项目节点结构TileMap设置图片资源备选图片添加物理碰撞添加y轴遮罩判断Y Sort Enable是干什么的&#xff1f; 脚本代码 前言 Godot 官方 教程 Godot 2d 官方案例C#重构 专栏 Godot 2d 重构 github地址 完成内容 项目节点结构 TileMap设置 图片资源 备选图…
阅读更多...
[Python]unittest-单元测试

[Python]unittest-单元测试

目录 unittest的大致构成: Test Fixture Test Case-测试用例 Test Suite-测试套件 Test Runner 批量执行脚本 makeSuite() TestLoader discover() 用例的执行顺序 忽略用例执行 skip skipIf skipUnless 断言 HTML测试报告 错误截图 unittest是python中的单元测…
阅读更多...
多个相同地址的I2C设备，如何挂载在同一条总线上

多个相同地址的I2C设备，如何挂载在同一条总线上

前言 &#xff08;1&#xff09;如果有嵌入式企业需要招聘湖南区域日常实习生&#xff0c;任何区域的暑假Linux驱动实习岗位&#xff0c;可C站直接私聊&#xff0c;或者邮件&#xff1a;zhangyixu02gmail.com&#xff0c;此消息至2025年1月1日前均有效 &#xff08;2&#xff0…
阅读更多...
NetSuite数据备份办法

NetSuite数据备份办法

本周有同学问有啥办法可以实现NetSuite的数据备份&#xff1f;这是个常见问题&#xff0c;今天总结一下。 我们认为可以选择的技术路线有下面几个&#xff1a; 从技术可行性、数据可利用角度&#xff0c;毫无疑问我们将推荐第三种办法。所以&#xff0c;今朝就介绍一下。 Ana…
阅读更多...
最新文章

Copyright @ 2022~2023