250. Count Univalue Subtrees
Дан корень бинарного дерева, return количество поддеревьев с одинаковыми значениями.
Подtree с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.
Example
Input: root = [5,1,5,5,5,null,5]
Output: 4
C# solution
matched/originalpublic class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int count = 0;
private bool Dfs(TreeNode node) {
if (node == null) {
return true;
}
bool isLeftUniValue = Dfs(node.left);
bool isRightUniValue = Dfs(node.right);
if (isLeftUniValue && isRightUniValue) {
if (node.left != null && node.left.val != node.val) {
return false;
}
if (node.right != null && node.right.val != node.val) {
return false;
}
count++;
return true;
}
return false;
}
public int CountUnivalSubtrees(TreeNode root) {
Dfs(root);
return count;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
class Solution {
public:
private int count = 0;
private bool Dfs(TreeNode node) {
if (node == null) {
return true;
}
bool isLeftUniValue = Dfs(node.left);
bool isRightUniValue = Dfs(node.right);
if (isLeftUniValue && isRightUniValue) {
if (node.left != null && node.left.val != node.val) {
return false;
}
if (node.right != null && node.right.val != node.val) {
return false;
}
count++;
return true;
}
return false;
}
public int CountUnivalSubtrees(TreeNode root) {
Dfs(root);
return count;
}
}Java solution
matched/originalclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int count = 0;
private boolean dfs(TreeNode node) {
if (node == null) {
return true;
}
boolean isLeftUniValue = dfs(node.left);
boolean isRightUniValue = dfs(node.right);
if (isLeftUniValue && isRightUniValue) {
if (node.left != null && node.left.val != node.val) {
return false;
}
if (node.right != null && node.right.val != node.val) {
return false;
}
count++;
return true;
}
return false;
}
public int countUnivalSubtrees(TreeNode root) {
dfs(root);
return count;
}
}JavaScript solution
matched/originalclass TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
constructor() {
this.count = 0;
}
dfs(node) {
if (node === null) {
return true;
}
const isLeftUniValue = this.dfs(node.left);
const isRightUniValue = this.dfs(node.right);
if (isLeftUniValue && isRightUniValue) {
if (node.left !== null && node.left.val !== node.val) {
return false;
}
if (node.right !== null && node.right.val !== node.val) {
return false;
}
this.count++;
return true;
}
return false;
}
countUnivalSubtrees(root) {
this.dfs(root);
return this.count;
}
}Python solution
matched/originalclass TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def __init__(self):
self.count = 0
def dfs(self, node):
if not node:
return True
isLeftUniValue = self.dfs(node.left)
isRightUniValue = self.dfs(node.right)
if isLeftUniValue and isRightUniValue:
if node.left and node.left.val != node.val:
return False
if node.right and node.right.val != node.val:
return False
self.count += 1
return True
return False
def countUnivalSubtrees(self, root):
self.dfs(root)
return self.countGo solution
matched/originalpackage main
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Solution struct {
count int
}
func (s *Solution) dfs(node *TreeNode) bool {
if node == nil {
return true
}
isLeftUniValue := s.dfs(node.Left)
isRightUniValue := s.dfs(node.Right)
if isLeftUniValue && isRightUniValue {
if node.Left != nil && node.Left.Val != node.Val {
return false
}
if node.Right != nil && node.Right.Val != node.Val {
return false
}
s.count++
return true
}
return false
}
func (s *Solution) CountUnivalSubtrees(root *TreeNode) int {
s.dfs(root)
return s.count
}Algorithm
1️⃣
Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0.
2️⃣
Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод returns логическое значение, указывающее, является ли подtree, укоренённое в этом узле, подtreeм с одинаковыми значениями. Выполните следующие действия в этом методе:
Если узел равен null, return true.
Рекурсивно проверьте, образует ли левый потомок подtree с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).
Рекурсивно проверьте, образует ли правый потомок подtree с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right).
Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, return false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, return false. В противном случае, увеличьте count на 1 и return true.
В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому tree, укоренённое в node, также не может быть таким подtreeм. return false.
3️⃣
return count.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.