第三周 递归、分治、树与图

题目数：23

本周作业

• 23.合并K 个升序链表 （Hard） (要求：用分治实现，不要用堆) 半年内出题频次：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 方法一：分治 渐进时间复杂度：O(kn×logk)，空间复杂度：O(logk)
func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if n == 0 {
        return nil
    } else if n == 1 {
        return lists[0]
    } else if n == 2 {
        return mergeTwoList(lists[0], lists[1])
    }
    mid := n >> 1
    return mergeTwoList(mergeKLists(lists[:mid]), mergeKLists(lists[mid:]))
}

func mergeTwoList(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    pre := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            pre.Next, l1 = l1, l1.Next
        } else {
            pre.Next, l2 = l2, l2.Next
        }
        pre = pre.Next
    }
    if l1 != nil {
        pre.Next = l1
    } else {
        pre.Next = l2
    }
    return dummy.Next
}
// 方法二：顺序合并 进时间复杂度为 O(k^2*n)

// 方法三：使用优先队列合并 时间复杂度: O(kn×logk), 空间复杂度: O(k)

• 47.全排列 II （Medium）半年内出题频次： 重点

// 递归、回溯
func permuteUnique(nums []int) (res [][]int) {
    sort.Ints(nums) // 排序
    n := len(nums)
    path := []int{}
    // 变量名：visited 或 used, 存储状态：make([]bool, n) 或 map[int]bool{}
    used := map[int]bool{}
    var recur func(int) // dfs、backtrack
    recur = func(level int) {
        // 递归终止条件
        if level == n {
            // 加入结果集
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := 0; i < n; i++ {
            // 寻找未使用元素
            // 当前已经使用 或 保证从左往右逐个填入
            if used[i] || i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            path = append(path, nums[i])
            used[i] = true
            recur(level + 1)
            used[i] = false // 恢复
            path = path[:len(path)-1]
        }
    }
    recur(0)
    return res
}

• 106.从中序与后序遍历序列构造二叉树 （Medium）半年内出题频次： 重点

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 方法一：递归
func buildTree(inorder []int, postorder []int) *TreeNode {
    idxMap := map[int]int{}
    for i, v := range inorder {
        idxMap[v] = i
    }
    var build func(int, int) *TreeNode
    build = func(inorderLeft, inorderRight int) *TreeNode {
        // 无剩余节点
        if inorderLeft > inorderRight {
            return nil
        }

        // 后序遍历的末尾元素即为当前子树的根节点
        val := postorder[len(postorder)-1]
        postorder = postorder[:len(postorder)-1]
        root := &TreeNode{Val: val}

        // 根据 val 在中序遍历的位置，将中序遍历划分成左右两颗子树
        // 由于我们每次都从后序遍历的末尾取元素，所以要先遍历右子树再遍历左子树
        inorderRootIndex := idxMap[val]
        root.Right = build(inorderRootIndex+1, inorderRight)
        root.Left = build(inorderLeft, inorderRootIndex-1)
        return root
    }
    return build(0, len(inorder)-1)
}
// 方法二：迭代
func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(postorder) == 0 {
        return nil
    }
    root := &TreeNode{Val: postorder[len(postorder)-1]}
    stack := []*TreeNode{root}
    inorderIndex := len(inorder) - 1
    for i := len(postorder) - 2; i >= 0; i-- {
        postorderVal := postorder[i]
        node := stack[len(stack)-1]
        if node.Val != inorder[inorderIndex] {
            node.Right = &TreeNode{Val: postorderVal}
            stack = append(stack, node.Right)
        } else {
            for len(stack) > 0 && stack[len(stack)-1].Val == inorder[inorderIndex] {
                node = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                inorderIndex--
            }
            node.Left = &TreeNode{Val: postorderVal}
            stack = append(stack, node.Left)
        }
    }
    return root
}

class Solution {

    HashMap<Integer,Integer> memo = new HashMap<>();
    int[] post;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i);
        post = postorder;
        TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);
        return root;
    }
	//1.左子树-中序数组 is = is, ie = ri - 1
	//2.左子树-后序数组 ps = ps, pe = ps + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长	度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
	//3.右子树-中序数组 is = ri + 1, ie = ie
	//4.右子树-后序数组 ps = ps + ri - is, pe - 1
    public TreeNode buildTree(int is, int ie, int ps, int pe) {
        if(ie < is || pe < ps) return null;

        int root = post[pe];
        int ri = memo.get(root);

        TreeNode node = new TreeNode(root);
        node.left = buildTree(is, ri - 1, ps, ps + ri - is - 1);
        node.right = buildTree(ri + 1, ie, ps + ri - is, pe - 1);
        return node;
    }
}

class Solution {
    private Map<Integer,Integer> pos = new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        for(int i = 0; i < n; i++)
            pos.put(inorder[i], i);  //记录中序遍历的根节点位置
        return dfs( inorder, postorder, 0, n - 1, 0, n - 1);   
    }
     public TreeNode dfs(int[] inorder, int[] postorder, int il, int ir,int pl, int pr)
    {
        if(pl > pr ) return null;
        int k = pos.get(postorder[pr]); //中序遍历根节点位置
        TreeNode root = new TreeNode(postorder[pr]); //创建根节点
        root.left  = dfs(inorder, postorder, il, k - 1, pl, pl + k - 1 - il);
        root.right = dfs(inorder, postorder, k + 1, ir, pl + k - 1 - il + 1, pr - 1);
        return root;     
    }
}

• 210.课程表 II （Medium）半年内出题频次：重点

// 深度优先遍历
func findOrder(numCourses int, prerequisites [][]int) []int {
    var (
        edegs = make([][]int, numCourses)
        visited = make([]int, numCourses)
        result = []int{}
        vaild = true
        dfs func(u int)
    )
    dfs = func(u int) {
        visited[u] = 1
        for _, c := range edegs[u] {
            if visited[c] == 0 {
                dfs(c)
                if !vaild {
                    return
                }
            } else if visited[c] == 1 {
                vaild = false
                return
            }
        }
        visited[u] = 2
        result = append(result, u)
    }
    for _, info := range prerequisites {
        edegs[info[1]] = append(edegs[info[1]], info[0])
    }

    for i := 0; i < numCourses && vaild; i++ {
        if visited[i] == 0 {
            dfs(i)
        }
    }
    if !vaild {
        return []int{}
    }
    for i := 0; i < numCourses/2; i++ {
        result[i], result[numCourses-i-1] = result[numCourses-i-1], result[i]
    }
    return result
}

// 广度优先遍历
func findOrder(numCourses int, prerequisites [][]int) []int {
    var (
        edges = make([][]int, numCourses)
        indeg = make([]int, numCourses)
        result = []int{}
    )
    for _, pre := range prerequisites {
        edges[pre[1]] = append(edges[pre[1]], pre[0])
        indeg[pre[0]]++
    }
    q := []int{}
    for i := 0; i < numCourses; i++ {
        if indeg[i] == 0 {
            q = append(q, i)
        }
    }
    for len(q) > 0 {
        course := q[0]
        q = q[1:]
        result = append(result, course)
        for _, c := range edges[course] {
            indeg[c]--
            if indeg[c] == 0 {
                q = append(q, c)
            }
        }
    }
    if len(result) == numCourses {
        return result
    }
    return []int{}
}

• 685.冗余连接 II （Hard）半年内出题频次： 重点

func findRedundantDirectedConnection(edges [][]int) (redundantEdge []int) {
    n := len(edges)
    uf := newUnionFind(n + 1)
    parent := make([]int, n+1) // parent[i] 表示 i 的父节点
    for i := range parent {
        parent[i] = i
    }

    var conflictEdge, cycleEdge []int
    for _, edge := range edges {
        from, to := edge[0], edge[1]
        if parent[to] != to { // to 有两个父节点
            conflictEdge = edge
        } else {
            parent[to] = from
            if uf.find(from) == uf.find(to) { // from 和 to 已连接
                cycleEdge = edge
            } else {
                uf.union(from, to)
            }
        }
    }

    // 若不存在一个节点有两个父节点的情况，则附加的边一定导致环路出现
    if conflictEdge == nil {
        return cycleEdge
    }
    // conflictEdge[1] 有两个父节点，其中之一与其构成附加的边
    // 由于我们是按照 edges 的顺序连接的，若在访问到 conflictEdge 之前已经形成了环路，则附加的边在环上
    // 否则附加的边就是 conflictEdge
    if cycleEdge != nil {
        return []int{parent[conflictEdge[1]], conflictEdge[1]}
    }
    return conflictEdge
}

type unionFind struct {
    ancestor []int
}

func newUnionFind(n int) unionFind {
    ancestor := make([]int, n)
    for i := 0; i < n; i++ {
        ancestor[i] = i
    }
    return unionFind{ancestor}
}

func (uf unionFind) find(x int) int {
    if uf.ancestor[x] != x {
        uf.ancestor[x] = uf.find(uf.ancestor[x])
    }
    return uf.ancestor[x]
}

func (uf unionFind) union(from, to int) {
    uf.ancestor[uf.find(from)] = uf.find(to)
}

实战例题

以下为课上实战例题

第 5 课 递归、分治

递归

• 78.子集 （Medium）半年内出题频次：

// 方法一：递归
func subsets(nums []int) (res [][]int) {
    n := len(nums)
    path := []int{}
    var dfs func(i int)
    dfs = func(i int) {
        if i == n {
            res = append(res, append([]int(nil), path...))
            return
        }
        // 不选
        dfs(i+1)
        // 选
        path = append(path, nums[i])
        dfs(i+1)
        path = path[:len(path)-1]
    }
    dfs(0)
    return res
}

// 迭代
func subsets(nums []int) (res [][]int) {
    n := len(nums)
    for mask := 0; mask < 1 << n; mask++ {
        set := []int{}
        for i, v := range nums {
            if mask >> i & 1 > 0 {
                set = append(set, v)
            }
        }
        res = append(res, set)
    }
    return res   
}

• 77.组合 （Medium）半年内出题频次：

// 方法一：递归
func combine(n int, k int) (res [][]int) {
    path := []int{}
    var dfs func(int)
    dfs = func(i int) {
        // 剪枝
        // if len(path) + (n - level + 1) < k {
        if k - len(path) > n - i + 1{
            return
        }
         if len(path) == k {
            res = append(res, append([]int(nil), path...))
            return
        }
        dfs(i+1)
        path = append(path, i)
        dfs(i+1)
        path = path[:len(path)-1]
    }
    dfs(1)
    return res
}

// 方法二：
func combine(n int, k int) (res [][]int) {
    path := []int{}
    var backtrack  func(int)
    backtrack = func(index int) {
        if len(path) == k {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := index; n - i + 1 >= k - len(path); i++ {
            path = append(path, i)
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }
    backtrack(1)
    return res
}

// 方法三：迭代

• 46.全排列 （Medium）半年内出题频次：

// 写法一：
func permute(nums []int) (res [][]int) {
    n := len(nums)
    var backtrack func(int)
    backtrack = func(level int) {
        if level == n {
            res = append(res, append([]int(nil), nums...))
            return
        }
        for i := level; i < n; i++ {
            nums[level], nums[i] = nums[i], nums[level]
            backtrack(level + 1)
            nums[level], nums[i] = nums[i], nums[level]
        }
    }
    backtrack(0)
    return res
}

// 写法二：
func permute(nums []int) (res [][]int) {
    n := len(nums)
    path := []int{}
    used := map[int]struct{}{}
    var backtrack func(int)
    backtrack = func(level int) {
        if level == n {
            res = append(res, append([]int(nil), path...))
            return
        }
        for i := 0; i < n; i++ {
            if _, ok := used[i]; !ok {
                path = append(path, nums[i])
                used[i] = struct{}{}
                backtrack(level + 1)
                delete(used, i)
                path = path[:len(path)-1]
            }
        }
    }
    backtrack(0)
    return res
}

树

• 226.翻转二叉树 （Easy）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

• 98.验证二叉搜索树 （Medium）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 方法一：
func isValidBST(root *TreeNode) bool {
    return valid(root, math.MinInt32, math.MaxInt32)
}

func valid(root *TreeNode, min, max int) bool {
    if root == nil {
        return true
    }
    if root.Val < min || root.Val > max {
        return false
    }
    return valid(root.Left, min, root.Val - 1) && valid(root.Right, root.Val + 1, max)
}

// 方法二：中序遍历，记录前一个元素
func isValidBST(root *TreeNode) bool {
    pre := math.MinInt64 // 初始化
    var inorderFunc func(root *TreeNode) bool
    inorderFunc = func(root *TreeNode) bool {
        if root == nil {
            return true
        }
        if !inorderFunc(root.Left) {
            return false
        }
        if pre >= root.Val {
            return false
        }
        pre = root.Val
        return inorderFunc(root.Right)
    }
    return inorderFunc(root)
}

// 中序迭代
func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    inorder := math.MinInt64
    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Val <= inorder {
            return false
        }
        inorder = root.Val
        root = root.Right
    }
    return true
}

• 104.二叉树的最大深度 （Easy）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 111.二叉树的最小深度 （Easy）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 方法一： bfs 迭代, 还可以增加count数组结合q一起使用
func minDepth(root *TreeNode) (min int) {
    if root == nil {
        return 0
    }
    q := []*TreeNode{root}
    for len(q) > 0 {
         min++
        for i := len(q); i > 0; i-- {
            node := q[0]
            if node.Left == nil && node.Right == nil {
                return min
            }
            q = q[1:]
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
    }
    return min
}

// 方法二: 递归
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    leftDepth, rightDepth := minDepth(root.Left), minDepth(root.Right)
    if leftDepth == 0 || rightDepth == 0 {
        return leftDepth + rightDepth + 1
    }
    return min(leftDepth, rightDepth) + 1
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

分治

• 50.Pow(x, n) （Medium）半年内出题频次：

func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n < 0 {
        n = -n
        x = 1 / x
    }
    pow := myPow(x, n >> 1)
    if n & 1 == 1 {
        return x * pow * pow
    } else {
        return pow * pow
    }
}

• 22.括号生成 （Medium）半年内出题频次：

// 递归
func generateParenthesis(n int) (ans []string) {
    var generate func(l , r int, path string)
    generate = func(l, r int, path string) {
        if l == n && r == n {
            ans = append(ans, path)
            return
        }
        if l < n {
            generate(l + 1, r, path + "(")
        }
        if r < l {
            generate(l, r + 1, path + ")")
        }
    }
    generate(0, 0, "")
    return ans
}

// 训练营：分治，重点理解
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) return {""};
        if (store.find(n) != store.end()) return store[n]; // 记忆化
        vector<string> ans;
        for (int k = 1; k <= n; k++) { // 加法原理
            vector<string> A = generateParenthesis(k - 1);
            vector<string> B = generateParenthesis(n - k);
            // S = (A)B
            // 乘法原理
            for (string& a : A)
                for (string& b : B)
                    ans.push_back("(" + a + ")" + b);

        }
        store[n] = ans;
        return ans;
    }
private:
    unordered_map<int, vector<string>> store;
};

第 6 课 树与图

树、二叉树、树的遍历

• 94.二叉树的中序遍历 （Easy）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 方法一：递归
func inorderTraversal(root *TreeNode) (ans []int) {
    var inorder func(root *TreeNode)
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inorder(root.Left)
        ans = append(ans, root.Val)
        inorder(root.Right)
    }
    inorder(root)
    return ans
}

// 方法二：颜色标记法（属于迭代）

// 方法三：迭代模拟栈

// 方法四：Morris 中序遍历

• 589.N 叉树的前序遍历 （Easy）半年内出题频次：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
// 方法一：递归
func preorder(root *Node) []int {
    ans := []int{}
    var dfs func(root *Node)
    dfs = func(root *Node) {
        if root == nil {
            return
        }
        ans = append(ans, root.Val)
        for _, children := range root.Children {
            dfs(children)
        }
        // 速度会更快
        //n := len(root.Children)
        //for i := 0; i < n; i++ {
        //    pre(root.Children[i])
        //}
    }
    dfs(root)
    return ans
}

// 方法二：迭代
func preorder(root *Node) []int {
    ans := []int{}
    if root == nil {
        return ans
    }
    stack := []*Node{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        ans = append(ans, node.Val)
        for i := len(node.Children) - 1; i >= 0; i-- {
            stack = append(stack, node.Children[i])
        }
    }
    return ans
}

• 429.N 叉树的层序遍历 （Medium）半年内出题频次：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
// 方法一：递归
func levelOrder(root *Node) (res [][]int) {
    var dfs func (*Node, int)
    dfs = func(root *Node, level int) {
        if root == nil {
            return
        }
        if len(res) < level + 1 {
            res = append(res, []int{})
        }
        res[level] = append(res[level], root.Val)
        for _, children := range root.Children {
            dfs(children, level + 1)
        }
    }
    dfs(root, 0)
    return res
}

// 方法二：迭代
func levelOrder(root *Node) (res [][]int) {
    if root == nil {
        return res
    }
    queue := []*Node{root}
    for len(queue) > 0 {
        levels := []int{}
        for n := len(queue); n > 0; n-- {
            node := queue[0]
            queue = queue[1:]
            levels = append(levels, node.Val)
            for _, children := range node.Children {
                queue = append(queue, children)
            }
        }
        res = append(res, levels)
    }
    return res
}

• 105.从前序与中序遍历序列构造二叉树 （Medium）半年内出题频次：

// 递归
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &TreeNode{Val: preorder[0]}
    mid := 0; 
    for root.Val != inorder[mid] {
        mid++
    }
    root.Left = buildTree(preorder[1:len(inorder[:mid])+1], inorder[:mid])
    root.Right = buildTree(preorder[len(inorder[:mid])+1:], inorder[mid+1:])
    return root
}
// 递归优化
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &TreeNode{Val: preorder[0]}
    mid := 0; 
    for root.Val != inorder[mid] {
        mid++
    }
    // 已下优化后版本
    root.Left = buildTree(preorder[1:mid+1], inorder[:mid])
    root.Right = buildTree(preorder[mid+1:], inorder[mid+1:])
    return root
}

// 训练营：递归
func buildTree(preorder []int, inorder []int) *TreeNode {
    m, n := len(preorder), len(inorder)
    var build func(int, int, int, int) *TreeNode
    build = func(l1, r1, l2, r2 int) *TreeNode {
        if l1 > r1 {
            return nil
        }
        root := &TreeNode{Val: preorder[l1]}
        // 可使用map进行优化
        mid := l2
        for inorder[mid] != root.Val {
            mid++
        }
        root.Left = build(l1 + 1, l1 + (mid - l2), l2, mid - 1)
        root.Right = build(l1 + (mid - l2) + 1, r1, mid + 1, r2)
        return root
    }
    return build(0, m - 1, 0, n - 1)
}

• 297.二叉树的序列化与反序列化 （Hard）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
    
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    sb := &strings.Builder{}
    var encode func(root *TreeNode)
    encode = func(root *TreeNode) {
        if root == nil {
            sb.WriteString("null,")
            return
        }
        //ans.WriteString(fmt.Sprintf("%d,", root.Val))
        sb.WriteString(strconv.Itoa(root.Val))
        sb.WriteByte(',')
        encode(root.Left)
        encode(root.Right)
    }
    encode(root)
    return sb.String()
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    sp := strings.Split(data, ",")
    var decode func() *TreeNode
    decode = func() *TreeNode {
        val := sp[0]
        sp = sp[1:]
        if val == "null" {
            return nil
        }
        v, _ := strconv.Atoi(val)
        return &TreeNode{v, decode(), decode()}
    }
    return decode()
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

树的直径、最近公共祖先、树的变形

• 树的直径 （Medium）（此题为 LeetCode 会员题选做）半年内出题频次：

** vip题 **

// edges = [[0, 1], [0, 2]]
func treeDiameter(edges [][]int) int {
  
}

// 训练营
class Solution {
	public:
  		int treeDiameter(vector<vector<int>> edges) {
            n = 0;
            for(vector<int>& edge := edges) {
                int x = edge[0];
                int y = edge[1];
                n = max(n, max(x, y));
            }
            n++;
            for (int i = 0; i < n; i++) to.push_back({});
            // 出边数组
            for(vector<int>& edge := edges) {
             	int x = edge[0];
                int y = edge[1];
                to[x].push_back(y);
                to[y].push_back(x);
            }
            int p = findFarthest(0).first;
            return findFarthest(p).second
        }
    private:
    	vector<vector<int>> to;
    	int n;
    	// <点， 距离>
    	pair<int, int> findFarthest(int start) {
            vector<int> depth(n, -1);
            queue<int> q;
            q.push(start);
            depth[start] = 0
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                for (int y : to[x]) {
                    if (depth[y] != -1) continue; // 走过了
                    depth[y] = depth[x] + 1;
                    q.push(y);
                }
            }
            int ans = start;
            for (int i = 0; i < n; i++) {
                if (depth[i] > depth[ans]) ans = i;
            }
            return {ans, depth[ans+1]}
        }
}

• 236.二叉树的最近公共祖先 （Medium）半年内出题频次：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil || root == p || root == q {
         return root
     }
     left := lowestCommonAncestor(root.Left, p, q)
     right := lowestCommonAncestor(root.Right, p, q)
     if left == nil {
         return right
     } else if right == nil {
         return left
     }
     return root
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 训练营
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        this->p = p;
        this->q = q;
        dfs(root);
        return ans;    
    }
private:
    TreeNode* p;
    TreeNode* q;
    TreeNode* ans;
    pair<bool, bool> dfs(TreeNode* root) {
        if (root == nullptr) return {false, false};
        pair<bool, bool> leftResult = dfs(root->left);
        pair<bool, bool> rightResut = dfs(root->right);
        pair<bool, bool> result;
        result.first = leftResult.first || rightResut.first || root->val == p->val;
        result.second = leftResult.second || rightResut.second || root->val == q->val;
        if (result.first && result.second && ans == nullptr) ans = root;
        return result;
    }
};

图、图的遍历

• 684.冗余连接 （Medium）半年内出题频次：

// 写法一：
func findRedundantConnection(edges [][]int) []int {
    parent := make([]int, len(edges) + 1)
    for i := range parent {
        parent[i] = i
    }
    find := func (p int) int {
        for parent[p] != p {
            parent[p] = parent[parent[p]]
            p = parent[p]
        }
        return p
    }
    union := func(x, y int) bool {
        px, py := find(x), find(y)
        if px == py  {
            return false
        }
        parent[px] = py
        return true
    }
    for _, edge := range edges {
        if !union(edge[0], edge[1]) {
            return edge
        }
    }
    return nil
}
// 写法二：
func findRedundantConnection(edges [][]int) []int {
    parent := make([]int, len(edges) + 1)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    union := func(from, to int) bool {
        x, y := find(from), find(to)
        if x == y {
            return false
        }
        parent[x] = y
        return true
    }
    for _, edge := range edges {
        if !union(edge[0], edge[1]) {
            return edge
        }
    }
    return nil
}
// 写法三：并查集独立抽象出去 https://leetcode-cn.com/submissions/detail/108890546/

// 参考训练营 c++ 写法
func findRedundantConnection(edges [][]int) []int {
    n := 0
    for _, edge := range edges {
        n = max(n, max(edge[0], edge[1]))
    }
    var (
        to = make([][]int, n + 1)
        visited = make([]bool, n + 1)
        hasCycle = false
        dfs func(x, fa int)
    )
    dfs = func(x, fa int) {
        visited[x] = true
        for _, y := range to[x] {
            if y == fa {
                continue
            }
            if !visited[y] {
                dfs(y, x)
            } else {
                hasCycle = true
            }
        }
        visited[x] = false
    }
    for _, edge := range edges {
        x, y := edge[0], edge[1]
        to[x] = append(to[x], y)
        to[y] = append(to[y], x)
        hasCycle = false
        dfs(x, 0)
        if hasCycle {
            return []int{x,y}
        }
    }
    return nil
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 207.课程表 （Medium）半年内出题频次：

func canFinish(numCourses int, prerequisites [][]int) bool {
    var (
        edges = make([][]int, numCourses)
        indeg = make([]int, numCourses)
        result = []int{}
    )
    for _, info := range prerequisites {
        edges[info[1]] = append(edges[info[1]], info[0])
        indeg[info[0]]++
    }
    q := []int{}
    for course, cnt := range indeg {
        if cnt == 0 {
            q = append(q, course)
        }
    }
    for len(q) > 0 {
        x := q[0]
        q = q[1:]
        result = append(result, x)
        for _, course := range edges[x] {
            indeg[course]--
            if indeg[course] == 0 {
                q = append(q, course)
            }
        }
    }
    return len(result) == numCourses
}

// 写法二：
func canFinish(numCourses int, prerequisites [][]int) bool {
    var (
        edges = make([][]int, numCourses)
        indeg = make([]int, numCourses)
        result []int
    )

    for _, info := range prerequisites {
        edges[info[1]] = append(edges[info[1]], info[0])
        indeg[info[0]]++
    }

    q := []int{}
    for i := 0; i < numCourses; i++ {
        if indeg[i] == 0 {
            q = append(q, i)
        }
    }

    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        result = append(result, u)
        for _, v := range edges[u] {
            indeg[v]--
            if indeg[v] == 0 {
                q = append(q, v)
            }
        }
    }
    return len(result) == numCourses
}