有无大佬指教一下算法
一颗二叉树,每个节点是红色或蓝色,如果一个节点(不包括自身)所在子树中,红色节点和蓝色节点个数相同,那么该节点是平衡节点。求整棵树一共有多少平衡节点?
我的思路是:递归,在每个节点里增加了两个变量分别表示它的子树中红色节点和蓝色节点的个数。递归返回时判断一下是否相等,相等就平衡节点数+1(虽然后来发现当时忘记写一个边界条件了
)
但是被批方向就错了,而且连递归的基本思路都没弄明白,不应该在节点里放临时变量表示颜色
想请教一下,怎么改进呀?或者不应该用递归?
(我算法菜狗,纠结了好久啥是所说的递归思想)
我的思路是:递归,在每个节点里增加了两个变量分别表示它的子树中红色节点和蓝色节点的个数。递归返回时判断一下是否相等,相等就平衡节点数+1(虽然后来发现当时忘记写一个边界条件了
但是被批方向就错了,而且连递归的基本思路都没弄明白,不应该在节点里放临时变量表示颜色
想请教一下,怎么改进呀?或者不应该用递归?
(我算法菜狗,纠结了好久啥是所说的递归思想)
全部评论
采用后序遍历,可以递归传递一个长度为2的一维数组,0和1分别表示红蓝的数量。再设一个全局变量用来记录平衡节点数量,当左[0]+右[0]等于左[1]+右[1]时候节点数量加一(要排除叶子节点),最后将两数组合并再加上当前的颜色,递归返回合并后的数组,over
我试了一下dfs可以呀,测了几个数据也通过了
二叉树,我记得牛客上就有不少二叉树的题
这是你的机试题?
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享