[LeetCode] 1361. Validate Binary Tree Nodes 验证二叉树

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Constraints:

• n == leftChild.length == rightChild.length
• 1 <= n <= 104
• -1 <= leftChild[i], rightChild[i] <= n - 1

这道题说是给了两个数组 leftChild 和 rightChild，其中 leftChild[i] 表示结点i的左子结点，rightChild[i] 表示结点i的右子结点，若值为 -1，表示没有左子结点或着右子结点，问给定的数组是否可以组成一个有效的二叉树。对于二叉树想必大家都不陌生，来看一下题目中给的例子，例子1是一棵有效的二叉树，例子2中由于结点3有两个父结点，所以不是有效的二叉树，例子3中两个结点互为父结点了，这也不是有效的二叉树。二叉树是一种特殊的有向图，一棵有效的二叉树至少要具备这个几个特点，首先是只有一个根结点，即所有结点必须是连成一个整体的，其次是每个结点最多有两个子结点，然后每个结点最多只有一个父结点，最后就是不能出现环。

有向图有个入度 In Degree 的概念，就是某个结点被其他结点连通的个数，对于有效二叉树来说，除了根结点之外的每个结点的入度必须是1，即每个结点最多只有一个父结点，根结点的入度是0，其没有父结点。那这里就可以通过计算每个结点的入度，来快速去除一些无效的二叉树，这里用个长度为n的入度数组 inDegree，然后遍历两个数组，若左子结点不为 -1，则将其入度值自增1，此时判断一下，若入度值大于1了，说明是无效的二叉树，返回 false，对右子结点进行相同的处理。

仅判断结点的入度值是不够的，比如例子3中，每个结点的入度都是1，但不是有效二叉树，因为其没有根结点，所以接下来需要找出根结点，而且只能有一个根结点，就是说只能有一个结点的入度是0，若找到了多个，则返回 false。找到了根结点后也还不能说就是有效的二叉函数了，还得保证所有的结点都是相连的，这个通过从根结点开始遍历二叉树，统计遍历到的结点个数，若成功遍历了n个结点，才能说是有效的二叉树。遍历的方法可以用 BFS 或者 DFS，这里先用 BFS，使用队列 queue 来辅助运算，先把根结点 root 放进去，然后进行 while 循环，每次从 queue 中取出一个结点，计数器 cnt 自增1，然后看其左右子结点，若存在就加入到队列中继续循环，最后判断 cnt 是否等于n即可，参见代码如下：

解法一：

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        int root = -1, cnt = 0;
        vector<int> inDegree(n);
        for (int i = 0; i < n; ++i) {
            int left = leftChild[i], right = rightChild[i];
            if (left != -1 && ++inDegree[left] > 1) return false;
            if (right != -1 && ++inDegree[right] > 1) return false;
        }
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] != 0) continue;
            if (root != -1) return false;
            root = i;
        }
        if (root == -1) return false;
        queue<int> q{{root}};
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            ++cnt;
            if (leftChild[t] != -1) q.push(leftChild[t]);
            if (rightChild[t] != -1) q.push(rightChild[t]);
        }
        return cnt == n;
    }
};

下面解法是用 DFS 来遍历二叉树，写起来更加简洁一些，在递归函数中首先判断若当前结点 node 为 -1，说明不存在，则返回0，否则分别对其左右子结点调用递归函数，将返回值加起来，再加上1，就是以当前结点 node 为根结点的二叉树的结点个数了，参见代码如下：

解法二：

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        int root = -1, cnt = 0;
        vector<int> inDegree(n);
        for (int i = 0; i < n; ++i) {
            int left = leftChild[i], right = rightChild[i];
            if (left != -1 && ++inDegree[left] > 1) return false;
            if (right != -1 && ++inDegree[right] > 1) return false;
        }
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] != 0) continue;
            if (root != -1) return false;
            root = i;
        }
        if (root == -1) return false;
        return countNodes(leftChild, rightChild, root) == n;
    }
    int countNodes(vector<int>& leftChild, vector<int>& rightChild, int node) {
        if (node == -1) return 0;
        return 1 + countNodes(leftChild, rightChild, leftChild[node]) + countNodes(leftChild, rightChild, rightChild[node]);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1361

参考资料：

https://leetcode.com/problems/validate-binary-tree-nodes/

https://leetcode.com/problems/validate-binary-tree-nodes/solutions/517557/c-find-root-dfs/

LeetCode All in One 题目讲解汇总(持续更新中...)