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-解题思路分析/