力扣_中级算法_树和图_4~6题_和_回溯算法_第1题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了力扣_中级算法_树和图_4~6题_和_回溯算法_第1题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7271字，纯文字阅读大概需要11分钟。
内容图文
一位C++小白的力扣刷题_成长记录_welcome to visit ^_^
树和图_第4题：填充每个节点的下一个右侧节点指针
题目描述：
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
举例 （反正，我是没看懂它这个例子 害.....）
示例：
输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},
"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,
"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":
{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":
{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},
"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},
"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
解题思路：搜索二叉树。这里又要用到递归。分两种情况来建立 next 关系。（详见代码）
学习心得：我先前想用一个队列，加一个vector容器来做，方法有点类似于昨天做的那个“二叉树的锯齿形
层次遍历”，但是有个地方一直有问题，用 VS2010 调试，还是没查出问题，后来去看题解，学习了前辈的
厉害的算法。二叉树，递归，嗯，两者紧密难分。
实现：（C++）
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if( root==NULL||root->left==NULL ) return root; //第二个条件“root->left==NULL”别忘了呦。因为本题的前提是“完美二叉树”嘛，left、right都可以
root->left->next=root->right; //细品
if( root->next!=NULL ) //这个是一环搭一环的“连”下去的。用草稿纸来画一画就一目了然了。
root->right->next=root->next->left;
connect( root->left ); //递归递归~这条语句和下面一条顺序不能换。因为next建立的关系是 从左至右 的
connect( root->right );
return root;
}
};
运行结果：
代码执行结果：
我的输入
[1,2,3,4,5,6,7]
我的答案
[1,#,2,3,#,4,5,6,7,#]
预期答案
[1,#,2,3,#,4,5,6,7,#]
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树和图_第5题：二叉搜索树中第K小的元素
题目描述：
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
举例：
示例 1:
输入: root = [3,1,4,null,2], k = 1 3 / 1 4 2 输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ 3 6
/ 2 4
/
1
输出: 3
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
解题思路：这道题做出来不难，用昨天学得的那个 迭代算法+一个队列+一个移动指针 来完成。
学习心得：这道题不难，但是想把 空间复杂度和时间复杂度 降低，还不时间松活事。我现在的目标就是
正确地把它做出来，其实我没用到那个，二叉搜索树的特征。虽然只打败了5%的人......嘻嘻。
实现：（C++）
/**
* 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:
int kthSmallest(TreeNode* root, int k) {
vector<int> vec; //容器，储存最后的数组
queue<TreeNode*> q;
TreeNode* fp; //定义一个“树”上的“移动”指针
q.push(root); //把“树根”放入队列
while( !q.empty() ) //只要队列里还有元素，继续循环
{
fp=q.front();
q.pop();
vec.push_back( fp->val );
if( fp->left ) //细品，作了图就好理解了
q.push(fp->left);
if( fp->right ) //细品+1
q.push(fp->right);
}
sort( vec.begin(),vec.end() ); //排序
return vec[k-1]; //排序后就好找了
}
};
运行结果：
我的输入
[3,1,4,null,2] 1
我的答案
1
预期答案
1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树和图_第6题：岛屿数量
题目描述：
给你一个由 ‘1‘（陆地）和 ‘0‘（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
举例：
示例 1:
输入: [ [‘1‘,‘1‘,‘1‘,‘1‘,‘0‘], [‘1‘,‘1‘,‘0‘,‘1‘,‘0‘], [‘1‘,‘1‘,‘0‘,‘0‘,‘0‘], [‘0‘,‘0‘,‘0‘,‘0‘,‘0‘] ] 输出: 1
示例 2:
输入: [ [‘1‘,‘1‘,‘0‘,‘0‘,‘0‘], [‘1‘,‘1‘,‘0‘,‘0‘,‘0‘], [‘0‘,‘0‘,‘1‘,‘0‘,‘0‘], [‘0‘,‘0‘,‘0‘,‘1‘,‘1‘] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题思路：“标记法”，我把它叫做标记法。就是 把出现 “1” 的上下左右换成另外一种字符。下次检索到 “1”（但被更换了的）时，就跳过。这个要结合递归函数。
力扣题解里，我看评论，看到一个很贴切的 名字 ，叫做 “感染函数” ，我觉得很应景。
学习心得：做这道题，让我明白了 ：在递归函数中，其终止条件一般放在最开始，而且这个 终止条件 一定
要做好。这道题 思维易理解，但是其 细节 需要我们 细品。
实现：（C++）
class Solution {
public:
void infect( vector<vector<char>>& g,int i,int j )
{
if( i<0||j<0||i>=g.size()||j>=g[0].size()||g[i][j]!=‘1‘) return ; //最后一个 终止小条件“ g[i][j]!=‘1‘ ”可别忘了
g[i][j]=‘*‘; //换个符号，做个标记
infect( g,i-1,j ); //递归 左边
infect( g,i,j+1 ); //递归 上边
infect( g,i+1,j ); //递归 右边
infect( g,i,j-1 ); //递归 下边
return ;
}
int numIslands(vector<vector<char>>& grid) {
if( grid.size()==0 ) return 0;
int row=grid.size(),col=grid[0].size();
int i,j,res=0;
for( i=0;i<row;i++ )
for( j=0;j<col;j++ )
{
if( grid[i][j]==‘1‘ )
{
res++; //有一个‘1‘，其岛屿数就加1
infect( grid,i,j );
}
}
return res;
}
};
运行结果：
代码执行结果：
我的输入
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
我的答案
1
预期答案
1
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
回溯算法_第1题： 电话号码的字母组合
题目描述：
注意:
你可以假设树中没有重复的元素。
举例：
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解题思路：
学习心得：（未写完）
实现：（C++）
/**
* 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 {
private:
unordered_map<int,int> index; //定义一个私有成员，哈希表。key为int类型，val也是int类型
public:
TreeNode* Tree( const vector<int>& preorder,const vector<int>& inorder,int pre_left,int pre_right,int in_left,int in_right) // 这里的两个 “&” 引用，可以减少很多很多空间！const 有没有无关紧要
{
if( pre_left>pre_right ) return nullptr; //终止条件
int pre_root_index=pre_left; //前序根结点的下标 即是 最左端（或左子树的最左端）的下标
int in_root_index=index[ preorder[pre_root_index] ]; //在中序数组中找到 与前序数组中根结点值相等的 元素的下标
int left_tree_size=in_root_index - in_left; //left_tree_size表示 中序数组中左子树的长度（和前序数组的左子树长度一样的）
TreeNode *root_1=new TreeNode( preorder[pre_root_index] ); //申请一个新的结点
root_1->left=Tree( preorder,inorder,pre_left+1,left_tree_size+pre_left,in_left,in_root_index-1); //要解释好这一句话，不轻松啊
//左子树递归。 前序数组的左边界、右边界相应在变；中序数组的左边界、右边界也相应在变。 关键是前序数组中 左子树的长度 和 中序数组中 左子树的长度是相同的。
root_1->right=Tree( preorder,inorder,left_tree_size+pre_left+1,pre_right,in_root_index+1,in_right); //右子树递归。（和左子树递归功能相似）
return root_1;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int i,n=preorder.size();
for( i=0;i<n;i++ ) //将中序数组中 每个元素(key)，对应到不同的(val)
index[ inorder[i] ]=i;
return Tree( preorder,inorder,0,n-1,0,n-1 );;
}
};
运行结果：
代码执行结果：
我的输入
[3,9,20,15,7] [9,3,15,20,7]
我的答案
[3,9,20,null,null,15,7]
预期答案
[3,9,20,null,null,15,7]
原文：https://www.cnblogs.com/Wang-dou-dou/p/13334139.html
内容总结
以上是互联网集市为您收集整理的力扣_中级算法_树和图_4~6题_和_回溯算法_第1题全部内容，希望文章能够帮你解决力扣_中级算法_树和图_4~6题_和_回溯算法_第1题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。