专栏首页Michael阿明学习之路LeetCode 250. 统计同值子树(递归)

LeetCode 250. 统计同值子树(递归)

1. 题目

给定一个二叉树,统计该二叉树数值相同的子树个数。

同值子树是指该子树的所有节点都拥有相同的数值。

示例:
输入: root = [5,1,5,5,5,null,5]

              5
             / \
            1   5
           / \   \
          5   5   5
输出: 4

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-univalue-subtrees 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
	int count = 0;
public:
    int countUnivalSubtrees(TreeNode* root) {
    	dfs(root);
    	return count;
    }
    bool dfs(TreeNode* root)
    {
    	if(!root) return true;
    	bool l = dfs(root->left);//左子树都一样吗?
    	bool r = dfs(root->right);
    	if(!l || !r || (root->left && root->val != root->left->val) 
    		||(root->right && root->val != root->right->val))		
		    return false;//左右子树有不一样 or root值跟左右不相等
        count++;
		return true;
    }
};

12 ms 16.3 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • LeetCode 222. 完全二叉树的节点个数(二分查找)

    说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底...

    Michael阿明
  • 程序员面试金典 - 面试题 04.05. 合法二叉搜索树(中序遍历)

    Michael阿明
  • 原 树莓派(raspberry)启用roo

    霡霂
  • LeetCode Weekly Contest 24 之 538.Convert BST to Greater Tree

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 查看linux里的initrd.img里的内容

    用户3765803
  • CentOS系统SSH免密后依然需要输入密码(已解决)

    1、问题 通过ssh-keygen -t rsa和ssh-copy-id -i node1操作后,免密登录依然需要输入密码。 [root@node1 ~]# s...

    程裕强
  • linux centos中添加删除修改环境变量,设置java环境变量

    前言 安装完软件必要添加环境变量。指令很少,然而长时间不写就会不自信:我写的对吗?于是百度开始,于是发现又是各有千秋。好吧,好记星不如烂笔头。当然,最重要的是,...

    Ryan-Miao
  • 手写AVL 树

    ShenduCC
  • 2 服务器基本情况

    Y大宽

扫码关注云+社区

领取腾讯云代金券