有无大佬指教一下算法

一颗二叉树,每个节点是红色或蓝色,如果一个节点(不包括自身)所在子树中,红色节点和蓝色节点个数相同,那么该节点是平衡节点。求整棵树一共有多少平衡节点?

我的思路是:递归,在每个节点里增加了两个变量分别表示它的子树中红色节点和蓝色节点的个数。递归返回时判断一下是否相等,相等就平衡节点数+1(虽然后来发现当时忘记写一个边界条件了

但是被批方向就错了,而且连递归的基本思路都没弄明白,不应该在节点里放临时变量表示颜色

想请教一下,怎么改进呀?或者不应该用递归?
(我算法菜狗,纠结了好久啥是所说的递归思想)
全部评论
1 回复 分享
发布于 2023-03-28 12:55 四川
采用后序遍历,可以递归传递一个长度为2的一维数组,0和1分别表示红蓝的数量。再设一个全局变量用来记录平衡节点数量,当左[0]+右[0]等于左[1]+右[1]时候节点数量加一(要排除叶子节点),最后将两数组合并再加上当前的颜色,递归返回合并后的数组,over
点赞 回复 分享
发布于 2023-03-30 00:10 四川
我试了一下dfs可以呀,测了几个数据也通过了
点赞 回复 分享
发布于 2023-03-28 11:11 河南
二叉树,我记得牛客上就有不少二叉树的题
点赞 回复 分享
发布于 2023-03-25 17:30 湖南
这是你的机试题?
点赞 回复 分享
发布于 2023-03-25 17:21 湖南

相关推荐

04-21 13:50
已编辑
北京理工大学 硬件测试
我们学校连夜发了声明,绝了绝了!看完了全部ppt,震碎三观。一般情况下我是站学生的,但这不是一般情况。这男的不能被取消学位吗?自己吃到了红利,靠着面试泄题得到的保研,又反手举报导师。这导师是《被举报系列》里最惨最恋爱脑的了,当然最可怜的是他的同妻……
牛客小黄鱼:看了ppt的聊天记录,真不知道谁才是受害者!有人为你剥过柚子吗?有人为你雪地里等你吗?有人为你写过情书吗?有人为你规划未来吗?有人为你小心翼翼吗?有人为你整页失眠失眠吗? 有人为你送上自己的科研成果吗?有人为你安排出国留学吗?有人愿意给你一个月2万吗?
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客企业服务