题目：验证二叉树
二叉树上有n个节点，按从0到n - 1编号，其中节点i的两个子节点分别
是leftChild[i]和rightChild[i]。
只有所有节点能够形成且只形成一颗有效的二叉树时，返回true；否则返回false。
如果节点i没有左子节点，那么leftChild[i]就等于-1。右子节点也符合该规则。注意：节点没有值，本问题中仅仅使用节点编号。
示例 1：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true
示例 2：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]输出：false
示例 3：
输入：n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出：false
示例 4：
输入：n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1, -1]
输出：false
提示：
•  1 <= n <= 10^4
•leftChild.length == rightChild.length == n
•-1 <= leftChild[i], rightChild[i] <= n - 1
语言:C++
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 (unt(leftChild[u])) {
return false;
}
seen.insert(leftChild[u]);
q.push(leftChild[u]);
}
if (rightChild[u] != -1) {
if (unt(rightChild[u])) {
二叉树的遍历pythonreturn false;
}
seen.insert(rightChild[u]);
q.push(rightChild[u]);
}
}
return seen.size() == n;
}
};
语言:Python
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
语言:golang
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，那么可以直返返回f alse了
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)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。