Bài toán

Link đến bài toán: 1361. Validate Binary Tree Nodes

Phân tích

Bài này khó nhất là hiểu xem đề bài muốn gì. Đề cho ta một list các node và cạnh của các node đó và muốn ta kiểm tra xem đó có phải là một cây nhị phân hợp lệ hay không. Điều kiện để các node này tạo thành một cây nhị phân hợp lệ là:

  • Có đúng 1 node là root
  • Các node khác đều có đúng 1 node cha
  • Các node không được tạo thành các chu trình

Để xác định 2 điều kiện sau, ta đơn giản kiểm ra số bậc trong (in-degree) của từng node là được:

  • Nếu có 2 node có in-degree = 0 thì đó không phải là cây nhị phân hợp lệ
  • Nếu có 1 node có in-degree > 1 thì đó không phải là cây nhị phân hợp lệ

Để kiểm tra điều kiện cuối cùng, ta sử dụng Union-Find/Disjoint Set để kiểm tra xem các node có liên thông với nhau hay không.

Giải thuật

Union-Find

type UnionFind struct {
	parent []int
	rank   []int
}

func (uf *UnionFind) init(n int) {
	uf.parent = make([]int, n)
	uf.rank = make([]int, n)
	for i := 0; i < n; i++ {
		uf.parent[i] = i
		uf.rank[i] = 1
	}
}

func (uf *UnionFind) find(x int) int {
	if uf.parent[x] == x {
		return x
	}
	uf.parent[x] = uf.find(uf.parent[x])
	return uf.parent[x]
}

func (uf *UnionFind) union(x, y int) bool {
	xp := uf.find(x)
	yp := uf.find(y)
	if xp == yp {
		return false
	}
	if uf.rank[xp] < uf.rank[yp] {
		uf.parent[xp] = yp
	} else if uf.rank[xp] > uf.rank[yp] {
		uf.parent[yp] = xp
	} else {
		uf.parent[yp] = xp
		uf.rank[xp]++
	}
	return true
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	inDegree := make([]int, n)
	for i := 0; i < n; i++ {
		if leftChild[i] != -1 {
			inDegree[leftChild[i]]++
		}
		if rightChild[i] != -1 {
			inDegree[rightChild[i]]++
		}
	}
	count := 0
	for i := 0; i < n; i++ {
		if inDegree[i] == 0 {
			count++
		}
	}
	if count != 1 {
		return false
	}

	isRootFound := false
	for i := 0; i < n; i++ {
		if inDegree[i] != 1 && isRootFound {
			return false
		} else if inDegree[i] == 0 {
			isRootFound = true
		}
	}

	uf := UnionFind{}
	uf.init(n)
	for i := 0; i < n; i++ {
		if leftChild[i] != -1 {
			if !uf.union(i, leftChild[i]) {
				return false
			}
		}
		if rightChild[i] != -1 {
			if !uf.union(i, rightChild[i]) {
				return false
			}
		}
	}

	root := uf.find(0)
	for i := 1; i < n; i++ {
		if uf.find(i) != root {
			return false
		}
	}

	return true
}

Độ phức tạp: O(n).