250. Count Univalue Subtrees

public 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;
    }
}

#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;
    }
}

class 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;
    }
}

class 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;
    }
}

class 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.count

package 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 логическое значение, указывающее, является ли подBaum, укоренённое в этом узле, подBaumм с одинаковыми значениями. Выполните следующие действия в этом методе:

Если узел равен null, return true.

Рекурсивно проверьте, образует ли левый потомок подBaum с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left).

Рекурсивно проверьте, образует ли правый потомок подBaum с одинаковыми значениями. Выполните 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.

В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому Baum, укоренённое в node, также не может быть таким подBaumм. return false.

3️⃣

return count.

😎