Question

1361. 验证二叉树

English Version

题目描述

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

 

提示：

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

解法

方法一：并查集

我们可以遍历每个节点 $i$ 以及对应的左右孩子 $l$, $r$，用 $vis$ 数组记录节点是否有父节点：

• 若孩子节点已存在父节点，说明有多个父亲，不满足条件，直接返回 false。
• 若孩子节点与父节点已经处于同一个连通分量，说明会形成环，不满足条件，直接返回 false。
• 否则，进行合并，并且将 $vis$ 数组对应位置置为 true，同时将连通分量个数减去 $1$。

遍历结束，判断并查集中连通分量个数是否为 $1$，若是返回 true，否则返回 false。

时间复杂度 $O(n \times \alpha(n))$，空间复杂度 $O(n)$。其中 $n$ 为节点个数，而 $\alpha(n)$ 为阿克曼函数的反函数，即反阿克曼函数，其值小于 $5$。

class Solution:
  def validateBinaryTreeNodes(
    self, n: int, leftChild: List[int], rightChild: List[int]
  ) -> bool:
    def find(x: int) -> int:
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    p = list(range(n))
    vis = [False] * n
    for i, (a, b) in enumerate(zip(leftChild, rightChild)):
      for j in (a, b):
        if j != -1:
          if vis[j] or find(i) == find(j):
            return False
          p[find(i)] = find(j)
          vis[j] = True
          n -= 1
    return n == 1

class Solution {
  private int[] p;

  public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    boolean[] vis = new boolean[n];
    for (int i = 0, m = n; i < m; ++i) {
      for (int j : new int[] {leftChild[i], rightChild[i]}) {
        if (j != -1) {
          if (vis[j] || find(i) == find(j)) {
            return false;
          }
          p[find(i)] = find(j);
          vis[j] = true;
          --n;
        }
      }
    }
    return n == 1;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
    int p[n];
    iota(p, p + n, 0);
    bool vis[n];
    memset(vis, 0, sizeof(vis));
    function<int(int)> find = [&](int x) {
      return p[x] == x ? x : p[x] = find(p[x]);
    };
    for (int i = 0, m = n; i < m; ++i) {
      for (int j : {leftChild[i], rightChild[i]}) {
        if (j != -1) {
          if (vis[j] || find(i) == find(j)) {
            return false;
          }
          p[find(i)] = find(j);
          vis[j] = true;
          --n;
        }
      }
    }
    return n == 1;
  }
};

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
  p := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  vis := make([]bool, n)
  for i, a := range leftChild {
    for _, j := range []int{a, rightChild[i]} {
      if j != -1 {
        if vis[j] || find(i) == find(j) {
          return false
        }
        p[find(i)] = find(j)
        vis[j] = true
        n--
      }
    }
  }
  return n == 1
}