从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)

简介: 从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145

以下题目更适合使用C++完成,难度也更大一些,所以放在这里。

文字解析能力有限,难理解的地方可以跟着代码画画图,或者看看官方题解。

606. 根据二叉树创建字符串 - 力扣(LeetCode)

难度简单

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

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

示例 1:


输入:root = [1,2,3,4]

输出:"1(2(4))(3)"

解释:初步转化后得到 "1(2(4)())(3()())" ,但省略所有不必要的空括号对后,字符串应该是"1(2(4))(3)" 。

示例 2:


输入:root = [1,2,3,null,4]

输出:"1(2()(4))(3)"

解释:和第一个示例类似,但是无法省略第一个空括号对,否则会破坏输入与输出一一映射的关系。

提示:

  • 树中节点的数目范围是 [1, 10^4]
  • -1000 <= Node.val <= 1000
/**
 * 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) {
 
    }
};

解析代码:

class Solution {
public:    // 这里的2有人当成to命名
    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;
    }
};

这段代码的缺陷就是传值返回,代价有点大,

改进就是写一个子函数去用引用返回,这里就不改了。

102. 二叉树的层序遍历 - 力扣(LeetCode)

难度中等

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

示例 1:


输入:root = [3,9,20,null,null,15,7]

输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]

输出:[[1]]

示例 3:

输入:root = []

输出:[]

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000
/**
 * 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) {
 
    }
};

解析代码:

以前用C语言讲的层序遍历

数据结构与算法⑯(第四章_下)二叉树的层序遍历+判断完全二叉树+一道OJ_GR C的博客-CSDN博客

现在我们有STL就不用自己弄一个队列了,而且可以对比一下选C语言给的代码和选C++给的,

就能体会到C++的方便了,C++写:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0; // 每一层的结点数量,因为要放在不同的vector中
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }
 
        vector<vector<int>> vv;
        while(!q.empty())
        {
            vector<int> v;
            while(levelSize--) // 控制一层一层出
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
 
                if(front->left) // 出完一个就入它的左右结点
                {
                    q.push(front->left);
                }
                if(front->right)
                {
                    q.push(front->right);
                }
                q.pop();
            }
            levelSize = q.size(); // 此时下一层的已入完,更新levelSize
            vv.push_back(v);
        }
        return vv;
    }
};

107. 二叉树的层序遍历 II - 力扣(LeetCode)

难度中等

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

示例 1:


输入:root = [3,9,20,null,null,15,7]

输出:[[15,7],[9,20],[3]]

示例 2:

输入:root = [1]

输出:[[1]]

示例 3:

输入:root = []

输出:[]

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000
/**
 * 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) {
 
    }
};

解析代码:

这题写过上面的,直接复制上面的代码,最后加一句reverse:

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0; // 每一层的结点数量,因为要放在不同的vector中
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }
 
        vector<vector<int>> vv;
        while(!q.empty())
        {
            vector<int> v;
            while(levelSize--) // 控制一层一层出
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
 
                if(front->left) // 出完一个就入它的左右结点
                {
                    q.push(front->left);
                }
                if(front->right)
                {
                    q.push(front->right);
                }
                q.pop();
            }
            levelSize = q.size(); // 此时下一层的已入完,更新levelSize
            vv.push_back(v);
        }
        reverse(vv.begin(),vv.end());
        return vv;
    }
};

236. 二叉树的最近公共祖先 - 力扣(LeetCode)

难度中等

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

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

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

输出:5

解释:节点5和节点4的最近公共祖先是节点5 。


因为根据定义最近公共祖先节点可以为节点本身。


示例 3:


输入:root = [1,2], p = 1, q = 2 输出:1

提示:

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同
  • p != q
  • pq 均存在于给定的二叉树中。
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
    }
};

从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中):https://developer.aliyun.com/article/1521950

目录
相关文章
|
19小时前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
4天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
4天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
4天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
8天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
9 0
|
8天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
8天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
16天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0
|
8天前
|
存储 C语言
C语言学习记录——动态内存函数介绍(malloc、free、calloc、realloc)
C语言学习记录——动态内存函数介绍(malloc、free、calloc、realloc)
16 1
|
21小时前
|
算法 Unix Linux
C语言随机数的产生(rand、srand、time函数细节讲解)
C语言随机数的产生(rand、srand、time函数细节讲解)