验证二叉树

/* 思路：
 * 1. 我们依然使用入度来判断是否存在有效的二叉树。
 * 2. 使用Java Stream来简化代码。
 * 3. 我们仍然会检查每个节点是否有且只有一个父节点。
 */

import java.util.stream.IntStream;
import java.util.Arrays;

public class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] inDegree = new int[n];
        IntStream.range(0, n).forEach(i -> {
            if (leftChild[i] != -1) inDegree[leftChild[i]]++;
            if (rightChild[i] != -1) inDegree[rightChild[i]]++;
        });
        // 检查是否存在且仅存在一个入度为0的根节点
        if (IntStream.of(inDegree).filter(i -> i == 0).count() != 1) return false;
        // 检查是否有入度大于1的节点
        if (IntStream.of(inDegree).anyMatch(i -> i > 1)) return false;
        // 检查是否有环
        boolean[] visited = new boolean[n];
        return !hasCycle(0, leftChild, rightChild, visited);
    }

    private boolean hasCycle(int node, int[] leftChild, int[] rightChild, boolean[] visited) {
        if (node == -1) return false;
        if (visited[node]) return true;
        visited[node] = true;
        if (hasCycle(leftChild[node], leftChild, rightChild, visited) || hasCycle(rightChild[node], leftChild, rightChild, visited)) {
            return true;
        }
        visited[node] = false;
        return false;
    }
}