这道题我没有什么好的思路,而且力扣给的函数形式看得有点懵,所以我找到一个相对好理解的题解,具体可以参考下方链接。
说明:
返回值:可以认为是一个动态分配的二维数组,行:树有几层就有几个int *指针,指向一个数组(存储了该层所有结点的值),列:每层结点的值
int ** rslt = 【int * | int * | int * | ...】
↓ ↓ ↓ ...
【int|int|...】 【int|int|...】 【int|int|...】
returnSize:用来返回二位数组的行树,即*returnSize = 有几层就赋值几
returnColumnSizes:用来返回每层结点的个数,用一维数组来存储每层结点个数,这个数组要我们分配,调用者来free。
不懂这个参数可以这样思考,如何要在函数内返回一个数组:
1、通过返回值:
int *p = f();
int *f(void) {
int *a = malloc(sizeof(int)*SIZE);
return a;
}
2、通过参数:
int *p = NULL;
f(p);
void f(int *a) {
a = malloc(sizeof(int)*SIZE);
}
上面这样可以吗?当然不行,所以,要通过返回值返回一个在函数内分配的数组需要这样:
int *p = NULL;
f(&p);
void f(int **a) {
*a = malloc(sizeof(int)*SIZE);
}
#define NODE_SIZE 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
int **rslt = NULL;
int *columnSize = NULL;
struct TreeNode *queue[NODE_SIZE] = {0}; /* 做队列使用 */
struct TreeNode *pNode = NULL;
int front = 0, rear = 0, pre_rear;
int i = 0, j = 0; /* i用来索引行,即层数,j用来索引列,即每层的结点个数 */
if (!root) {
*returnSize = 0;
return NULL;
}
queue[rear++] = root; /* 先把root结点入队 */
while (front < rear) { /* 外层循环:用来处理队列,队列不为空就循环处理 */
pre_rear = rear; /* 备份上一层的队尾指针 */
rslt = realloc(rslt, (i + 1)*sizeof(int *)); /* 外层循环实际就是层数,每次扩充1 */
rslt[i] = calloc(pre_rear - front, sizeof(int));
while(front < pre_rear) { /* 内层循环:遍历每一层结点,每次出队一个结点,同时并把该结点的孩子入队 */
pNode = queue[front++]; /* 出队 */
rslt[i][j++] = pNode->val; /* 存储结点值 */
if (pNode->left) /* 当前结点左、右孩子存在则将他们入队 */
queue[rear++] = pNode->left;
if (pNode->right)
queue[rear++] = pNode->right;
}
columnSize = realloc(columnSize, (i + 1)*sizeof(int)); /* columnSize数组用来存储每层结点个数 */
columnSize[i++] = j;
j = 0;
}
*returnSize = i; /* 如上注释,这个参数用来“带回”层数 */
*returnColumnSizes = columnSize; /* 这个参数用来“带回”每层的结点个数 */
return rslt; /* 返回值存储了遍历的结果,上面两个参数用来描述这个结果,以便调用者打印树的形态 */
}
题目建议:这道题目 一些做过的同学 理解的也不够深入,建议大家先看我的视频讲解,无论做过没做过,都会有很大收获。
题目链接/文章讲解/视频讲解:代码随想录
想要翻转它,其实就把每一个节点的左右孩子交换一下就可以了。
关键在于遍历顺序,前中后序应该选哪一种遍历顺序? (一些同学这道题都过了,但是不知道自己用的是什么顺序)
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
注意只要把每一个节点的左右孩子翻转一下,就可以达到整体翻转的效果
这道题目使用前序遍历和后序遍历都可以,唯独中序遍历不方便,因为中序遍历会把某些节点的左右孩子翻转了两次!建议拿纸画一画,就理解了
那么层序遍历可以不可以呢?依然可以的!只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的!
我们下文以前序遍历为例,通过动画来看一下翻转的过程:
我们来看一下递归三部曲:
1)确定递归函数的参数和返回值
参数就是要传入节点的指针,不需要其他参数了,通常此时定下来主要参数,如果在写递归的逻辑中发现还需要其他参数的时候,随时补充。
返回值的话其实也不需要,但是题目中给出的要返回root节点的指针,可以直接使用题目定义好的函数,所以就函数的返回类型为TreeNode*
。
TreeNode* invertTree(TreeNode* root)
2)确定终止条件
当前节点为空的时候,就返回。
if (root == NULL) return root;
3)确定单层递归的逻辑
因为是先前序遍历,所以先进行交换左右孩子节点,然后反转左子树,反转右子树。
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
struct TreeNode* invertTree(struct TreeNode* root){
if(!root)
return NULL;
//交换结点的左右孩子(中)
struct TreeNode* temp = root->right;
root->right = root->left;
root->left = temp;
左
invertTree(root->left);
//右
invertTree(root->right);
return root;
}
题目建议:先看视频讲解,会更容易一些。
题目链接/文章讲解/视频讲解:代码随想录
首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点!
对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。
那么如何比较呢?
比较的是两个子树的里侧和外侧的元素是否相等。如图所示:
那么遍历的顺序应该是什么样的呢?
本题遍历只能是“后序遍历”,因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点,所以准确的来说是一个树的遍历顺序是左右中,一个树的遍历顺序是右左中。
但都可以理解算是后序遍历,尽管已经不是严格上在一个树上进行遍历的后序遍历了。
其实后序也可以理解为是一种回溯,当然这是题外话,讲回溯的时候会重点讲的。
说到这大家可能感觉我有点啰嗦,哪有这么多道理,上来就干就完事了。别急,我说的这些在下面的代码讲解中都有身影。
那么我们先来看看递归法的代码应该怎么写。
递归三部曲
1)确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下:
bool compare(TreeNode* left, TreeNode* right)
2)确定终止条件
要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。
节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)
此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:
此时左右节点不为空,且数值也不相同的情况我们也处理了。
代码如下:
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里我没有使用else
注意上面最后一种情况,我没有使用else,而是else if, 因为我们把以上情况都排除之后,剩下的就是 左右节点都不为空,且数值相同的情况。
3)确定单层递归的逻辑
此时才进入单层递归的逻辑,单层递归的逻辑就是处理 左右节点都不为空,且数值相同的情况。
代码如下:
bool outside = compare(left->left, right->right); // 左子树:左、 右子树:右
bool inside = compare(left->right, right->left); // 左子树:右、 右子树:左
bool isSame = outside && inside; // 左子树:中、 右子树:中(逻辑处理)
return isSame;
如上代码中,我们可以看出使用的遍历方式,左子树左右中,右子树右左中,所以我把这个遍历顺序也称之为“后序遍历”(尽管不是严格的后序遍历)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool compare(struct TreeNode* left,struct TreeNode* right){
if(left!=NULL && right==NULL) return false;
else if(left==NULL && right!=NULL) return false;
else if(left==NULL && right==NULL) return true;
else if(left->val!=right->val) return false;
bool out=compare(left->left,right->right);
bool in=compare(left->right,right->left);
bool compareLeaf=in && out;
return compareLeaf;
}
bool isSymmetric(struct TreeNode* root) {
if(root==NULL) return true;
return compare(root->left,root->right);
}
如果你有问题或者有其他想法,欢迎评论区留言,大家可以一起探讨。
文章浏览阅读2w次,点赞7次,收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案,在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建:添加Visual C++ , Win32 项目这......_c#调用lib
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体,挺好看的。注重颜值的网站都会使用,例如知乎:font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时,向何处发送表单中的数据,地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理,get方式直接显示在url地址中,数据可以被缓存,且长度有限制;而post方式数据隐藏传输,_html表单的处理程序有那些
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证(即Google Authenticator服务)后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
文章浏览阅读4.3k次,点赞5次,收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节,实现了多层数据的堆叠,为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制(CoW)策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的,不建议用于生成环境。_docker 保存容器
文章浏览阅读834次,点赞27次,收藏13次。网络拓扑结构是指计算机网络中各组件(如计算机、服务器、打印机、路由器、交换机等设备)及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式,也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
文章浏览阅读1.8k次,点赞5次,收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时,通常的做法是:new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的,而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠,也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑,需要做一些额外的特殊处理,笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数,一劳永逸,避免每次ne_date.prototype 将所有 ios
文章浏览阅读5.3k次。方法一:用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头,使全列成选中状态,然后粘贴,最后commit提交即可。(前提..._excel导入pl/sql
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,包括untracked的文件...
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
文章浏览阅读1.8k次。版权声明:转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数