golang 解法, 执行用时: 36 ms, 内存消耗: 6.6 MB, 提交时间: 2023-06-13 10:06:10

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	inc := make([]int, n) // 记录每个结点的入度
	for i := 0; i < n; i++ { // 开始遍历左右子树数组
		// 如果i结点的左子树或者右子树是自身，那是不行的，可以直接返回false
		if leftChild[i] == i || rightChild[i] == i {
			return false
		}
		if n := leftChild[i]; n != -1 { // 开始填充每个结点的入度
			inc[n]++
		}

		if n := rightChild[i]; n != -1 { // 同上
			inc[n]++
		}
	}
	zeroc := 0 // 入度为0的个数（正常树的话，这个结点最后的值应该是1）
	for _, n := range inc {
		// 如果有入度大于2的结点或者入度为0的结点不止一个，那么可以直接返回false了
		if n > 1 || zeroc > 1 {
			return false
		}
		if n == 0 { // 入度为0，
			zeroc++
		}
	}
	if zeroc != 1 { // 入度为0的结点不止一个，直接返回false
		return false
	}
	// 代码到这，说明现在已经满足了 入度为0的结点只有一个，剩余n-1个结点的入度都为1
	// 但是，还不能轻易返回，因为可能会有环，
	// 例如：leftChild=[1,0,3,-1], rightChild=[-1,-1,-1,-1]
	//      +--+0       2
	//      |   ^       +
	//      |   |       |
	//      v   |       v
	//      1 +-+       3
	// 所以下面，我们需要检测一下是否有环
	// 首先，我们需要把着两个数组合并一下，把非-1的值合并到一个数组上。为什么要这样做呢？
	// 可知leftChild=[1,0,3,-1], rightChild=[-1,-1,-1,-1]，这个是有环的
	// 那么leftChild=[1,-1,3,-1], rightChild=[-1,0,-1,-1]，这个也是有环的，
	// 但是因为leftChild[1]处的0跑到rightChild[1]处去了，导致我们不好检测
	for i := 0; i < n; i++ {
		inc[i] = leftChild[i]
		if inc[i] == -1 && rightChild[i] != -1 {
			inc[i] = rightChild[i]
		}
	}
	// 我们复用inc数组，合并之后inc = [1,0,3,-1]了
	// 从每一个结点出发， 进行环路检测。我们每遍历一个值会将其置为一个负数，标记已经遍历
	for i := 0; i < n; i++ {
		if inc[i] < 0 { // 已经遍历过，那么从下一个结点再出发
			continue
		}
		j := i // 当前结点没遍历过，那么从当前结点出发
		for inc[j] >= 0 { // 如果访问到的结点大于0，
			tmp := j
			j = inc[j]    // 那么让j去往下一个子结点
			inc[tmp] = -(i+2) // 当前结点置一下访问标记
			// 这里-（i+2）为第i轮的访问标记，为什么要区分轮次呢？
			// 因为如果不区分轮次，统一用负值标记，就会导致这么一个情况
			// - 假设第1轮的1号结点是非根结点，那么在遍历之后会将其置为一个负值，假设为-2；
			// - 那么如果第2轮的2号结点是1号结点的父节点，它访问到1号结点时发现1号结点已经被访问过，那么会做出错误判断有环。
			//   其实1号结点是先访问的，两次访问都不是在同一轮里。
		}

		if inc[j] == -(i+2) { // 用当前轮次的访问标记判断一下当前j结点是否已经访问过。
			return false // 如果当前轮次，该结点已经访问过，说明有环，直接返回false
		}
	}
	return true // 检查都无误后，返回true
}

golang 解法, 执行用时: 380 ms, 内存消耗: 8.4 MB, 提交时间: 2023-06-13 10:05:46

/**
 * 递归标记
 * 因为有n个结点，编号0~n-1，那么我们可以从这个n个结点分别出发，进行递归遍历。
 * 每次遍历都用一个长度为n标记数组记录一下某个结点被访问到的次数，
 * 一旦在遍历过程中，发现某个结点被访问的次数大于1，说明有环，那么直接返回false；
 * 遍历完成后，检查标记数组的每个值，有且仅有一个下标的值为0，
 * 也就是被访问次数为0（该下标对应结点为根节点），那么就可以返回true。
 */
func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	res := true
	// dontCheck顾名思义，不需要再检查了，标识着已经有结点有大于1的入度，
	// 那么不用检查可以直接返回false了
	dontCheck = false
	for i := 0; i < n; i++ {  // 每个结点都出发遍历一次
		res = true
		// 标记数组，记录每个结点被遍历的次数。因为每次这个数组都需要清空，我这里直接创新的了
		visited = make([]int, n) 
		check(i, leftChild, rightChild) // 递归
		if dontCheck {        // 如果dontCheck为true，那么可以直返返回false了
			res = false       // 置结果为false，break
			break
		}
		for _, n := range visited { // 检查一下标记数组的里面的值
			// 如果这次遍历有没有访问到的结点，说明这个结构有可能不是树，
			//也有可能因为我们没有从根节点出发，导致根节点没有访问到
			if n == 0 {
				// 我们没法判断，所以还是把res置为false，继续下一轮遍历
				res = false      
				break
			}
		}
		// 如果res为true，说明我们从i这个地方遍历，所有的结点都被我们访问了一次，
		// 那么这个结点就是树了，马上跳出循环返回true
		if res {  
			break
		}
	}
	return res
}

var visited []int
var dontCheck bool

func check(i int, leftChild, rightChild []int){
	// 如果已经dontCheck了，那么不需要继续递归了，直接返回。
	// 如果visited[i]已经被访问过一次了，现在又访问到，说明这个结点入度大于1了，也需要直接返回
	if dontCheck || visited[i] == 1 { 
		dontCheck = true
		return
	}
	visited[i] = 1 // 标记一下，我们访问了i结点
	if leftChild[i] != -1 { // 如果i结点有左子树，递归访问左子树
		check(leftChild[i], leftChild, rightChild)
	}
	if rightChild[i] != -1 { // 如果i结点有右子树，递归访问右子树
		check(rightChild[i], leftChild, rightChild)
	}
}

java 解法, 执行用时: 13 ms, 内存消耗: 43.5 MB, 提交时间: 2023-06-13 10:03:59

class Solution {
    // 并查集用的集合列表
    List<Integer> p = new ArrayList<>();
    // 用于统计不相交的连通分支个数
    int cnt;
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        // 用于标记各个孩子的父节点
        int[] father = new int[n];
        // 初始化
        Arrays.fill(father, -1);
        // 初始化并查集集合状态
        for(int i = 0; i < n; i++) p.add(i);
        // 初始化分支数
        cnt = n;
        // 遍历所有节点
        for(int i = 0; i < n; i++) {
            // 如果节点存在两个孩子，而且两个孩子相同，那么显然是错误的二叉树
            if(leftChild[i] == rightChild[i] && leftChild[i] != -1) return false;
            // 合并两个孩子
            if(!merge(father, i, leftChild[i]) || !merge(father, i, rightChild[i])) return false;
        }

        // 如果最后所有的节点组成一个连通分支，才是一棵树
        if(cnt == 1) return true;
        return false;

    }
    // 和并父亲和孩子节点，并判断逻辑
    private boolean merge(int[] father, int f, int c) {
        // 孩子是空的，直接返回
        if(c == -1) return true;
        // 孩子之前有爸爸了，就是错的
        if(father[c] != -1) return false;
        // 并查集查找两个集合的根
        int a = find(f), b = find(c);
        // 如果孩子和父亲已经存在于一个集合中，那么说明会产生环，返回错误
        if(a == b) return false;
        // 合并两个集合
        p.set(a, b);
        // 标记孩子的父亲是谁
        father[c] = f;
        // 连通分支数减一
        cnt --;
        return true;
    }
    // 并查集通用方法，找集合的根元素
    private int find(int x) {
        if(p.get(x) != x) {
            p.set(x, find(p.get(x)));
        }
        return p.get(x);
    }
}

cpp 解法, 执行用时: 44 ms, 内存消耗: 35.7 MB, 提交时间: 2023-06-13 10:03:22

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> indeg(n);
        for (int i = 0; i < n; ++i) {
            if (leftChild[i] != -1) {
                ++indeg[leftChild[i]];
            }
            if (rightChild[i] != -1) {
                ++indeg[rightChild[i]];
            }
        }

        int root = -1;
        for (int i = 0; i < n; ++i) {
            if (!indeg[i]) {
                root = i;
                break;
            }
        }
        if (root == -1) {
            return false;
        }

        unordered_set<int> seen;
        queue<int> q;
        seen.insert(root);
        q.push(root);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (leftChild[u] != -1) {
                if (seen.count(leftChild[u])) {
                    return false;
                }
                seen.insert(leftChild[u]);
                q.push(leftChild[u]);
            }
            if (rightChild[u] != -1) {
                if (seen.count(rightChild[u])) {
                    return false;
                }
                seen.insert(rightChild[u]);
                q.push(rightChild[u]);
            }
        }

        return seen.size() == n;
    }
};

python3 解法, 执行用时: 72 ms, 内存消耗: 18 MB, 提交时间: 2023-06-13 10:03:02

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        indeg = [0] * n
        for u in leftChild:
            if u != -1:
                indeg[u] += 1
        for u in rightChild:
            if u != -1:
                indeg[u] += 1
        
        root = -1
        for i in range(n):
            if indeg[i] == 0:
                root = i
                break
        if root == -1:
            return False

        
        seen = set([root])
        q = collections.deque([root])

        while len(q) > 0:
            u = q.popleft()
            if leftChild[u] != -1:
                if leftChild[u] in seen:
                    return False
                seen.add(leftChild[u])
                q.append(leftChild[u])
            if rightChild[u] != -1:
                if rightChild[u] in seen:
                    return False
                seen.add(rightChild[u])
                q.append(rightChild[u])
        
        return len(seen) == n