题目

二叉树上有 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

解题思路分析

1、层序遍历；时间复杂度O(n)，空间复杂度O(n)

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      if leftChild[i] != -1 {
         arr[leftChild[i]]++
      }
      if rightChild[i] != -1 {
         arr[rightChild[i]]++
      }
   }
   root := -1 // 寻找一个根节点
   for i := 0; i < n; i++ {
      if arr[i] == 0 {
         root = i
         break
      }
   }
   if root == -1 {
      return false
   }
   visited := make(map[int]bool)
   visited[root] = true
   queue := make([]int, 0)
   queue = append(queue, root)
   for len(queue) > 0 { // 层序遍历
      node := queue[0]
      queue = queue[1:]
      a, b := leftChild[node], rightChild[node]
      if a != -1 {
         if visited[a] == true {
            return false
         }
         visited[a] = true
         queue = append(queue, a)
      }
      if b != -1 {
         if visited[b] == true {
            return false
         }
         visited[b] = true
         queue = append(queue, b)
      }
   }
   return len(visited) == n
}

2、并查集；时间复杂度O(nlog(n))，空间复杂度O(n)

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
   fa = Init(n)
   for i := 0; i < n; i++ {
      a, b := leftChild[i], rightChild[i]
      if a != -1 {
         if find(a) != a || query(i, a) == true {
            return false
         }
         union(a, i) // 注意顺序
      }
      if b != -1 {
         if find(b) != b || query(i, b) == true {
            return false
         }
         union(b, i) // 注意顺序
      }
   }
   return getCount() == 1
}

var fa []int
var count int

// 初始化
func Init(n int) []int {
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      arr[i] = i
   }
   count = n
   return arr
}

// 查询
func find(x int) int {
   if fa[x] != x {
      fa[x] = find(fa[x])
   }
   return fa[x]
}

// 合并
func union(i, j int) {
   x, y := find(i), find(j)
   if x != y {
      fa[x] = y
      count--
   }
}

func query(i, j int) bool {
   return find(i) == find(j)
}

func getCount() int {
   return count
}

总结

Medium题目，二叉树题目