首页 > 代码库 > LeetCode-Count Univalue Subtrees
LeetCode-Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,
5 / 1 5 / \ 5 5 5
return 4
.
Solution:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public class UniValueCount { int value; boolean isUniValue; int count; public UniValueCount(int v, boolean is, int num){ value = v; isUniValue = is; count = num; } } public int countUnivalSubtrees(TreeNode root) { UniValueCount res = countUnivalRecur(root); return res.count; } public UniValueCount countUnivalRecur(TreeNode cur){ if (cur==null){ return new UniValueCount(0,false,0); } if (cur.left==null && cur.right==null){ return new UniValueCount(cur.val,true,1); } UniValueCount res = new UniValueCount(0,true,0); if (cur.left!=null){ UniValueCount leftRes = countUnivalRecur(cur.left); res.isUniValue = res.isUniValue && (leftRes.isUniValue && cur.val==leftRes.value); res.count += leftRes.count; } if (cur.right!=null){ UniValueCount rightRes = countUnivalRecur(cur.right); res.isUniValue = res.isUniValue && (rightRes.isUniValue && cur.val==rightRes.value); res.count += rightRes.count; } if (res.isUniValue){ res.count++; res.value = cur.val; } return res; }}
LeetCode-Count Univalue Subtrees
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。