LEETCODE 250. Count Univalue Subtrees 解题思路分析

题目大意:

统计同值子树

给定一棵二叉树,请统计出所有的同值子树。

同值子树的定义为:该子树的所有节点值相同。

示例:

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

              5
             / \
            1   5
           / \   \
          5   5   5

输出: 4

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=250

解题思路分析:

从树的顶点向下递归,如果该节点与其左右子节点的值都相同,并且左右子树都是同值树,那么当前树也是同值树,结果加一。递归结束条件是叶子节点,叶子节点肯定是同值树,结果加一。

实现代码:

int res=0; // 返回结果
public int countUnivalSubtrees(TreeNode root) {
    if(root==null) return 0; // 根节点为空,返回0
    helper(root); // 递归求解
    return res;
}
// 返回当前树是否为同值树
boolean helper(TreeNode root){
    // 如果是叶子节点
    if(root.left==null&&root.right==null){
        res++; // 返回结果加一
        return true; // 返回true
    }
    boolean isUni=true; // 当前树是否是同值树
    if(root.left!=null){ // 左子树不为空
        isUni &= helper(root.left); // 查看左子树是否是同值树
        isUni &= root.val==root.left.val; // 常看当前节点是否等于左节点
    }
    if(root.right!=null){ // 右子树不为空
        isUni &= helper(root.right); // 查看右子树是否是同值树
        isUni &= root.val==root.right.val; // 常看当前节点是否等于右节点
    }
    if(isUni) res++; // 当前树是同值树,结果加一
    return isUni; // 返回当前树是否是同值树
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Univalue Subtrees.

Memory Usage: 39.8 MB, less than 42.86% of Java online submissions for Count Univalue Subtrees.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-250-count-univalue-subtrees-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。