2022-03-15：给定一棵树的头节点head，原本是一棵正常的树， 现在，在树上多加了一条冗余的边， 请找到这条冗余的边并返回。

答案2022-03-15：

1.指向头，入度没有0的。入度没有2的。 2.未指向头，某一个点入度一定是2。 2.1.左右双全是父节点，另一个不全的不是父节点。 2.2.如果都不全，任选一个。 并查集。如果边两边的点在同一个集合，说明是冗余的。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	edges := [][]int{{1, 2}, {1, 3}, {2, 3}}
	ret := findRedundantDirectedConnection(edges)
	fmt.Println(ret)
}
func findRedundantDirectedConnection(edges [][]int) []int {
	// N是点的数量
	// 点的编号，1~N，没有0
	N := len(edges)
	// 并查集！N个点，去初始化，每个点各自是一个集合
	uf := NewUnionFind(N)
	// pre[i] = 0 来到i节点是第一次
	// pre[i] = 6 之前来过i，是从6来的！
	pre := make([]int, N+1)
	// 如果，没有入度为2的点，
	// first second 都维持是null
	// 如果，有入度为2的点，那么也只可能有一个
	// 比如入度为2的点，是5
	// first = [3,5]
	// second = [12,5]
	var first []int
	var second []int
	// 有没有环！非常不单纯！含义复杂！
	var circle []int
	for i := 0; i < N; i++ { // 遍历每条边！
		from := edges[i][0]
		to := edges[i][1]
		if pre[to] != 0 { // 不止一次来过to！
			first = []int{pre[to], to}
			second = edges[i]
		} else { // 第一次到达to，
			pre[to] = from
			if uf.same(from, to) {
				circle = edges[i]
			} else {
				uf.union(from, to)
			}
		}
	}
	// 重点解析！这是啥？？？
	// first != null
	// 有入度为2的点！
	return twoSelectOne(first != nil, twoSelectOne(circle != nil, first, second), circle)
}

func twoSelectOne(c bool, a, b []int) []int {
	if c {
		return a
	} else {
		return b
	}
}

type UnionFind struct {
	f []int
	s []int
	h []int
}

func NewUnionFind(N int) *UnionFind {
	ans := &UnionFind{}
	ans.f = make([]int, N+1)
	ans.s = make([]int, N+1)
	ans.h = make([]int, N+1)
	for i := 0; i <= N; i++ {
		ans.f[i] = i
		ans.s[i] = 1
	}
	return ans
}

func (this *UnionFind) find(i int) int {
	hi := 0
	for i != this.f[i] {
		this.h[hi] = i
		hi++
		i = this.f[i]
	}
	for hi > 0 {
		hi--
		this.f[this.h[hi]] = i
	}
	return i
}

func (this *UnionFind) same(i, j int) bool {
	return this.find(i) == this.find(j)
}

func (this *UnionFind) union(i, j int) {
	fi := this.find(i)
	fj := this.find(j)
	if fi != fj {
		if this.s[fi] >= this.s[fj] {
			this.f[fj] = fi
			this.s[fi] = this.s[fi] + this.s[fj]
		} else {
			this.f[fi] = fj
			this.s[fj] = this.s[fi] + this.s[fj]
		}
	}
}

执行结果如下：

在这里插入图片描述

左神java代码