更多干货就在我的个人博客 BlackBlog.tech http://blackblog.tech/ 欢迎关注!
也可以关注我的 csdn 博客: 黑哥的博客 https://blog.csdn.net/HeiGe__
谢谢大家!
网上大部分 LeetCode 的代码都没有给出注释和解释, 对于新手学习很不方便. 笔者在这里尽力给每一句代码都写上注释, 每一道题最后都有解释.
很久都没有刷 LeetCode 了, 上次 LeetCode 已经快是两个月之前的事情了. 现在继续. 之前中级算法差不多刷完了, 这次专练数据结构. 这一篇主要是 dfs 题目, 标识为简单的题目一般就跳过了, 主要刷中等与困难题.
LeetCode 上分类为 dfs 的题目大多数与树相关.
给个目录:
LeetCode98 验证二叉搜索树
LeetCode113 路径总和 II
LeetCode105 从前序与中序遍历序列构造二叉树
LeetCode106 从中序与后序遍历序列构造二叉树
LeetCode129 求根到叶子节点数字之和
LeetCode124 二叉树中的最大路径和
LeetCode130 被围绕的区域
LeetCode114 二叉树展开为链表
LeetCode116 填充同一层的兄弟节点
LeetCode117 填充同一层的兄弟节点 II
最后还有一波福利, 一个 TreeLinkNode 的建树调试代码, 官方没有给出, 自己搞了一份方便大家调试.
LeetCode98 验证二叉搜索树
题目
给定一个二叉树, 判断其是否是一个有效的二叉搜索树.
一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数.
节点的右子树只包含大于当前节点的数.
所有左子树和右子树自身必须也是二叉搜索树.
示例 1:
输入:
- 2
- / \
- 1 3
输出: true
示例 2:
输入:
- 5
- / \
- 1 4
- / \
- 3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6].
根节点的值为 5 , 但是其右子节点值为 4 .
C++ 代码
- class Solution {
- public:
- bool isValidBST(TreeNode* root) {
- return dfs(root,LONG_MAX,LONG_MIN);
- }
- bool dfs(TreeNode* root, long max,long min){
- if(!root) return true;
- if(root->val<=min || root->val>=max) return false;
- else return (dfs(root->left,root->val,min) && dfs(root->right,max,root->val));
- }
- };
体会
这个题利用了二叉检索树自身的性质, 左边节点小于根节点, 右边节点大于根节点. 初始化时带入系统最大值和最小值, 在递归过程中换成它们自己的节点值, 用 long 代替 int 就是为了包括 int 的边界条件.
如果这棵树遍历到了叶节点, 则返回 true. 如果在遍历的过程中出现了当前节点大于等于父节点 (左子树) 或小于等于父节点 (右子树) 则返回 false. 对结果做 && 运算. 返回最终的结果.
LeetCode113 路径总和 II
题目
给定一个二叉树和一个目标和, 找到所有从根节点到叶子节点路径总和等于给定目标和的路径.
说明: 叶子节点是指没有子节点的节点.
示例:
给定如下二叉树, 以及目标和 sum = 22,
- 5
- / \
- 4 8
- // \
- 11 13 4
- / \ / \
- 7 2 5 1
返回:
- [
- [5,4,11,2],
- [5,8,4,5]
- ]
C++ 代码
- class Solution {
- public:
- vector<vector<int>> res; // 最终结果
- vector<int> mark; // 每一个小的路径和
- vector<vector<int>> pathSum(TreeNode* root, int sum) {
- dfs(root,sum,0);
- return res;
- }
- void dfs(TreeNode* root,int sum,int now){
- if(!root) return;// 叶节点直接返回
- if(sum == now+root->val && root->left == NULL && root->right == NULL){ // 路经总和满足要求 且该节点是叶节点
- mark.push_back(root->val); // 首先将当前节点添加进 mark
- res.push_back(mark); // 将 mark 添加到 res 中
- mark.pop_back(); // 将当前值从 mark 中弹出, 因为节点结束
- return; // 返回
- }
- else{
- int tmp = now + root->val; // 如果路径还不满足 继续遍历 先左后右
- mark.push_back(root->val); // 把当前节点的值放入 mark
- dfs(root->left,sum,tmp);// 遍历左节点
- dfs(root->right,sum,tmp);// 遍历右节点
- mark.pop_back();// 弹出当前节点
- return;
- }
- }
- };
体会
思路比较清晰, 用 dfs 遍历整个树, 一旦遇到叶节点且数据总和满足 sum, 则将这个路径保存到最终结果. 中间使用 mark 记录路径, res 保存最终符合条件的路径. 注意记录路径的过程中, mark 中的数字要 pop.
LeetCode105 从前序与中序遍历序列构造二叉树
题目
根据一棵树的前序遍历与中序遍历构造二叉树.
注意:
你可以假设树中没有重复的元素.
例如, 给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
- 3
- / \
- 9 20
- / \
- 15 7
C++ 代码
- class Solution {
- public:
- TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
- if(preorder.size()==0 && inorder.size()==0) return NULL; // 前序后序都为空, 直接 return NULL
- return myBuildTree(preorder,inorder,0,0,inorder.size()-1);
- }
- TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder,int prestart,int instart,int inend){
- //prestart 代表当前子树的根节点在 preorder 的位置, instart inend 表示当前子树在 inorder 中的开头和结尾
- if ( prestart>preorder.size()-1 || inend <instart) return NULL; // 如果 inend<instart 或者 prestart 超过了 preorder 的限制 表示叶节点, 直接 return NULL
- TreeNode *root = new TreeNode(preorder[prestart]); // 新建一个节点 root 当前子树的根节点
- int inindex = 0; // 用于标记根节点的值在前序中的位置
- // 找 inindex 的位置
- for(int i=instart;i<=inend;i++){
- if(inorder[i] == preorder[prestart]){
- inindex = i;
- break;
- }
- }
- // 左子树, prestart 后移动一位, instart 不变, inend 为 inindex-1
- root->left = myBuildTree(preorder,inorder,prestart+1,instart,inindex-1);
- // 右子树, prestart 变为 prestart+inindex-instart+1, 也就是向后移动其在中序遍历中的位置离开头的距离后 + 1,inend 不变, instart 变为 inindex+1
- root->right = myBuildTree(preorder,inorder,prestart+inindex-instart+1,inindex+1,inend);
- // 将子树的根节点返回
- return root;
- }
- };
体会
使用先序遍历与中序遍历重建二叉树. 通过先序遍历, 我们很好确定根节点. 通过根节点在中序遍历中的位置, 我们可以确定一个树的左子树, 与右子树. 对左子树, 右子树做递归操作, 每次都计算出根节点, 将根节点与其父节点连接即可.
本题的解法利用元素下标来确定子树的先序和中序遍历, 也可以新建 vector 模拟这个过程, 但是比较耗时.
唯一可能的难点就是右子树建立时 prestart 的计算
LeetCode106 从中序与后序遍历序列构造二叉树
题目
根据一棵树的中序遍历与后序遍历构造二叉树.
注意:
你可以假设树中没有重复的元素.
例如, 给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
- 3
- / \
- 9 20
- / \
- 15 7
C++ 代码
- class Solution {
- public:
- TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
- if(inorder.size()==0 && postorder.size()==0) return NULL; // 中序 后序都为空, 则直接返回 NULL
- return myBuildTree(inorder,postorder,postorder.size()-1,0,inorder.size()-1); // 建树
- }
- TreeNode* myBuildTree(vector<int>& inorder,vector<int>& postorder,int poststart,int instart,int inend){
- //poststart 代表当前子树的根节点在 postorder 的位置, instart inend 表示当前子树在 inorder 中的开头和结尾
- if(instart>inend || poststart<0) return NULL; // 如果 instart>inend 或者 poststart<0 证明是叶节点, 返回 NULL
- TreeNode *root = new TreeNode(postorder[poststart]); // 新建一个子树的根节点
- int inindex=0;// 表示根节点在 inorder 中的位置
- // 寻找 inindex 的具体值
- for(int i=0;i<inorder.size();i++){
- if(inorder[i]==postorder[poststart]){
- inindex = i;
- break;
- }
- }
- // 建立左子树 poststart 向前移动 inend-inindex 位后再向前移动一位, instart 不变, inend 变为 inindex-1
- root->left = myBuildTree(inorder,postorder,poststart-1-(inend-inindex),instart,inindex-1);
- // 建立右子树 poststart 向前移动 1 位, instart 变为 inindex+1, inend 保持不变
- root->right = myBuildTree(inorder,postorder,poststart-1,inindex+1,inend);
- // 将子树的根节点返回
- return root;
- }
- };
体会
整体流程与上一题类似
使用中序遍历与后序遍历重建二叉树. 通过后序遍历, 我们很好确定根节点. 通过根节点在中序遍历中的位置, 我们可以确定一个树的左子树, 与右子树. 对左子树, 右子树做递归操作, 每次都计算出根节点, 将根节点与其父节点连接即可.
唯一可能的难点就是左子树建立时 prestart 的计算
LeetCode129 求根到叶子节点数字之和
题目
给定一个二叉树, 它的每个结点都存放一个 0-9 的数字, 每条从根到叶子节点的路径都代表一个数字.
例如, 从根到叶子节点路径 1->2->3 代表数字 123.
计算从根到叶子节点生成的所有数字之和.
说明: 叶子节点是指没有子节点的节点.
示例 1:
输入: [1,2,3]
- 1
- / \
- 2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此, 数字总和 = 12 + 13 = 25.
示例 2:
输入: [4,9,0,5,1]
- 4
- / \
- 9 0
- / \
- 5 1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此, 数字总和 = 495 + 491 + 40 = 1026.
C++ 代码
- class Solution {
- public:
- vector<int> path; // 记录每次的路径
- int sum_all = 0; // 数字总和
- int sumNumbers(TreeNode* root) {
- dfs(root); //dfs 开始
- return sum_all; // 直接返回路径和
- }
- void dfs(TreeNode* root){
- if(!root) return; // 如果是空节点直接返回
- if(root->left==NULL && root->right ==NULL){ // 如果是叶节点
- path.push_back(root->val); // 现将 val 存入 path
- sum_all += count(path); // 计算这一个 path 的数字和
- path.pop_back(); // 弹出 value
- }
- else{ // 如果不是叶节点
- path.push_back(root->val); // 将当前节点存入 path
- dfs(root->left); // 遍历左子树
- dfs(root->right); // 遍历右子树
- path.pop_back(); // 左右子树遍历完成后 这个根节点用完了 弹出
- return; // 终止递归
- }
- }
- int count(vector<int> vec){ // 将 vec 转换为数字
- int sum = 0;
- int power = 1;
- for(int i=vec.size()-1;i>=0;i--){
- sum += power*vec[i];
- power *=10;
- }
- return sum;
- }
- };
体会
这个题目与 113 比较类似.
都是遍历树, 记录下来路径. 这个题遍历到叶节点之后, 将记录的路径转换和数字, 将所有路径的数字进行求和, 最终输出整个树的数字和.
LeetCode124 二叉树中的最大路径和
题目
给定一个非空二叉树, 返回其最大路径和.
本题中, 路径被定义为一条从树中任意节点出发, 达到任意节点的序列. 该路径至少包含一个节点, 且不一定经过根节点.
示例 1:
输入: [1,2,3]
- 1
- / \
- 2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
- -10
- / \
- 9 20
- / \
- 15 7
输出: 42
C++ 代码
- class Solution {
- public:
- int Max;
- int maxPathSum(TreeNode* root) {
- if(root == NULL) return 0; // 根节点为空 直接返回
- Max = INT_MIN; // 将 MAX 初始化为一个极小的值
- dfs(root); //dfs
- return Max; // 返回最大值
- }
- int dfs(TreeNode* root){
- if(root==NULL) return 0; // 节点为 NULL 直接返回
- int left = dfs(root->left); // 遍历左子树
- int right = dfs(root->right); // 遍历右子树
- Max = max(Max,root->val+max(0,left)+max(0,right)); // 计算当前的 Max Max 为左子树最大路径的值 + 右子树最大路径的值 + 根节点的值
- return max(0,max(left,right))+root->val; // 返回 左子树 或者 右子树 中最大不分叉路径的值.
- }
- };
体会
这个题被划分到了困难题, 其实还是有一些巧妙的.
首先我们观察一下题目中给的样例, 不能发现. 这个题不能够用之前我们写的求根节点到任意叶节点的路径和的思路去解答. 因为最大值很可能是叶节点到叶节点的.
这个题我们需要设定一个 MAX 作为最后的结果, 遍历节点的左子树和右子树, 将左子树的最大不分叉路径(大于 0)+ 右子树的最大不分叉路径(大于 0)+ 节点本身的值与当前最大路径和 Max 作比较, 将较大的数保存于 MAX.dfs 返回的是左子树或者右子树最大不分叉路径的值, 最终结果返回 MAX 即可.
建议手动调试一遍, 理解更深入.
LeetCode130 被围绕的区域
题目
给定一个二维的矩阵, 包含'X' 和'O'(字母 O).
找到所有被'X' 围绕的区域, 并将这些区域里所有的'O' 用'X' 填充.
示例:
- X X X X
- X O O X
- X X O X
- X O X X
运行你的函数后, 矩阵变为:
- X X X X
- X X X X
- X X X X
- X O X X
解释:
被围绕的区间不会存在于边界上, 换句话说, 任何边界上的'O' 都不会被填充为'X'. 任何不在边界上, 或不与边界上的'O' 相连的'O' 最终都会被填充为'X'. 如果两个元素在水平或垂直方向相邻, 则称它们是 "相连" 的.
C++ 代码
- class Solution {
- public:
- void solve(vector<vector<char>>& board) {
- if(board.size()==0) return ;
- // 遍历第一行与最后一行
- for(int i=0;i<board[0].size();i++){
- dfs(board,0,i);
- dfs(board,board.size()-1,i);
- }
- // 遍历第一列与最后一列
- for(int i=0;i<board.size();i++){
- dfs(board,i,0);
- dfs(board,i,board[0].size()-1);
- }
- // 将所有标为 A 的地方填充为 O, 剩下的为 X
- for(int i=0;i<board.size();i++){
- for(int j=0;j<board[0].size();j++){
- if(board[i][j]=='A') board[i][j]='O';
- else board[i][j]='X';
- }
- }
- }
- void dfs(vector<vector<char>>& board,int x,int y){
- // 注意, 先判定边界, 再进行访问, 不然可能会出现数组越界的情况
- if(x<board.size() && x>=0 && y<board[0].size() &&y>=0 && board[x][y]=='O'){
- board[x][y]='A';
- dfs(board,x-1,y);
- dfs(board,x+1,y);
- dfs(board,x,y-1);
- dfs(board,x,y+1);
- }
- return;
- }
- };
体会
看到这个题, 我们首先会想到, 遍历数组, 对每一个 O 做连通区域的判断. 但是这样做非常麻烦. 我们可以转换一下思路, 遍历边缘的点, 如果是 O 的话, 将它所联通的区域标为 A. 最后将所有为 A 的点标为 O, 剩下的点全是 X.
LeetCode114 二叉树展开为链表
题目
给定一个二叉树, 原地将它展开为链表.
例如, 给定二叉树
- 1
- / \
- 2 5
- / \ \
- 3 4 6
将其展开为:
- 1
- \
- 2
- \
- 3
- \
- 4
- \
- 5
- \
- 6
C++ 代码
- class Solution {
- public:
- void flatten(TreeNode* root) {
- dfs(root);
- l2r_reverse(root);
- }
- void dfs(TreeNode* root){
- if(isLeaf(root) || root==NULL) return;
- else {
- dfs(root->left);
- dfs(root->right);
- move(root);
- }
- }
- // 判断一个节点是否是叶节点
- bool isLeaf(TreeNode* root){
- if(!root) return false;
- if(root->left==NULL && root->right==NULL) return true;
- else return false;
- }
- // 将该节点右子树的所有内容全部放到左子树最后一个节点的下面
- void move(TreeNode* root){
- // 如果有左子树找 到左子树的最后一个节点
- if(root->left!=NULL) {
- TreeNode *tmp = root->left;
- while (tmp->left) {
- tmp = tmp->left;
- }
- tmp->left = root->right;
- root->right = NULL;
- }
- else{ // 如果左子树不存在, 直接将右子树的变为左子树
- root->left = root->right;
- root->right = NULL;
- }
- }
- // 将单线的左子树 完全 变为右子树
- void l2r_reverse(TreeNode* root){
- if(!root)
- return;
- l2r_reverse(root->left);
- if(root->left!=NULL &&root->right==NULL){
- root->right = root->left;
- root->left = NULL;
- return;
- }
- }
- };
体会
这个题比较有趣. 我采用的方法是 (虽然我感觉我搞复杂了) 从下开始, 将每一个父节点的右子树放到左子树最后一个节点下面. 通过这个方法最后会得到一个向左偏的单链表, 我们再将这个树旋转为向右偏, 得到最后的链表.
LeetCode116 填充同一层的兄弟节点
题目
给定一个二叉树
- struct TreeLinkNode {
- TreeLinkNode *left;
- TreeLinkNode *right;
- TreeLinkNode *next;
- }
填充它的每个 next 指针, 让这个指针指向其下一个右侧节点. 如果找不到下一个右侧节点, 则将 next 指针设置为 NULL.
初始状态下, 所有 next 指针都被设置为 NULL.
说明:
你只能使用额外常数空间.
使用递归解题也符合要求, 本题中递归程序占用的栈空间不算做额外的空间复杂度.
你可以假设它是一个完美二叉树(即所有叶子节点都在同一层, 每个父节点都有两个子节点).
示例:
给定完美二叉树,
- 1
- / \
- 2 3
- / \ / \
- 4 5 6 7
调用你的函数后, 该完美二叉树变为:
- 1 -> NULL
- / \
- 2 -> 3 -> NULL
- / \ / \
- 4->5->6->7 -> NULL
C++ 代码
- class Solution {
- public:
- void connect(TreeLinkNode *root) {
- dfs(root);
- }
- void dfs(TreeLinkNode* root){
- if(!root) return;// 如果节点为空就返回
- if(root->left && root->right){ // 如果节点的左右节点都存在(题目已经说了都存在 不判断也可以)
- root->left->next = root->right; // 直接连接
- if(root->next) root->right->next = root->next->left; // 这个是用来连接 5 和 6 的
- else root->right->next = NULL;// 这个是用来连接 7 与 NULL
- }
- dfs(root->left);// 递归
- dfs(root->right);// 递归
- }
- };
体会
这个题目比较简单, 直接模拟这个过程就可以, 代码也比较短.
LeetCode117 填充同一层的兄弟节点 II
题目
给定一个二叉树
- struct TreeLinkNode {
- TreeLinkNode *left;
- TreeLinkNode *right;
- TreeLinkNode *next;
- }
填充它的每个 next 指针, 让这个指针指向其下一个右侧节点. 如果找不到下一个右侧节点, 则将 next 指针设置为 NULL.
初始状态下, 所有 next 指针都被设置为 NULL.
说明:
你只能使用额外常数空间.
使用递归解题也符合要求, 本题中递归程序占用的栈空间不算做额外的空间复杂度.
示例:
给定二叉树,
- 1
- / \
- 2 3
- / \ \
- 4 5 7
调用你的函数后, 该二叉树变为:
- 1 -> NULL
- / \
- 2 -> 3 -> NULL
- / \ \
- 4-> 5 -> 7 -> NULL
C++ 代码
- class Solution {
- public:
- void connect(TreeLinkNode *root) {
- //start 用于连接两个层, 其 next 为下一个层的首元素
- //tmp 用来遍历整个树
- //tmp 始终比 root 低一层
- TreeLinkNode * start = new TreeLinkNode(0);
- TreeLinkNode * tmp = start; //tmp 指向 start (很重要, 用来连接下一层)
- while(root){
- // 如果根节点存在左节点, tmp 与根节点的左节点连接 修改 tmp 到同层下一个节点 对一个每一层第一个元素, 这个步骤完成了 start 与下层第一个元素的连接
- if(root->left){
- tmp->next = root->left;
- tmp = tmp->next;
- }
- // 如果根节点存在右节点, tmp 与根节点的右节点连接, 修改 tmp 到同层下一个节点
- if(root->right){
- tmp->next = root->right;
- tmp = tmp->next;
- }
- root = root->next;//root 向同层下一个节点移动
- // 如果 root 不存在, 证明这一层遍历完了, 我们修改 root 变为下一层第一个节点, 修改 start 后为 NULL,tmp 重新指向 start(很重要, 用来连接下一层)
- if(!root){
- root = start->next;
- start->next = NULL;
- tmp = start;
- }
- }
- }
- };
体会
这个题是 116 的通常形式. 说实话, 这个题写了很久, 最后还是错了. 看了网上的同解, 觉得写的很巧妙. 网上的代码基本没有注释, 我在这里把注释补全, 方便大家. 强烈建议自己手动调试一遍.
附录
对于 116 117 所给出的代码, LeetCode 上面没有给出调试的环境, 和所依赖的函数.
我根据之前建树的代码写了一份 116 117,TreeLinkNode 的根据字符串建树的代码, 下面放到这里, 大家自取.
- #include <iostream>
- #include <string>
- #include <queue>
- #include <vector>
- #include <sstream>
- using namespace std;
- struct TreeLinkNode {
- int val;
- TreeLinkNode *left, *right, *next;
- TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
- };
- void trimLeftTrailingSpaces(string &input) {
- input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
- return !isspace(ch);
- }));
- }
- void trimRightTrailingSpaces(string &input) {
- input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
- return !isspace(ch);
- }).base(), input.end());
- }
- TreeLinkNode* stringToTreeNode(string input) {
- trimLeftTrailingSpaces(input);
- trimRightTrailingSpaces(input);
- input = input.substr(1, input.length() - 2);
- if (!input.size()) {
- return nullptr;
- }
- string item;
- stringstream ss;
- ss.str(input);
- getline(ss, item, ',');
- TreeLinkNode* root = new TreeLinkNode(stoi(item));
- queue<TreeLinkNode*> nodeQueue;
- nodeQueue.push(root);
- while (true) {
- TreeLinkNode* node = nodeQueue.front();
- nodeQueue.pop();
- if (!getline(ss, item, ',')) {
- break;
- }
- trimLeftTrailingSpaces(item);
- if (item != "null") {
- int leftNumber = stoi(item);
- node->left = new TreeLinkNode(leftNumber);
- nodeQueue.push(node->left);
- }
- if (!getline(ss, item, ',')) {
- break;
- }
- trimLeftTrailingSpaces(item);
- if (item != "null") {
- int rightNumber = stoi(item);
- node->right = new TreeLinkNode(rightNumber);
- nodeQueue.push(node->right);
- }
- }
- return root;
- }
- int main(){
- TreeLinkNode * root;
- root = stringToTreeNode("{2,1,3,0,7,9,1,2,null,1,0,null,null,8,8,null,null,null,null,7}");
- }
来源: http://www.jianshu.com/p/3955a2efdf2d