LiSheng's blog
lisheng
2024-09-10
目录

链表和树

# 链表

定义： 类型：单链表、双向链表、循环链表

// 有可能面试需要自定义链表
type ListNode struct {
    Val int
    Next *ListNode
}
1
2
3
4
5

# 链表高频题

# 移除链表元素

# 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

哈希表哈希func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    cur := head
    for cur!=nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}
1
2
3
4
5
6
7
8
9
10
11

# K 个一组翻转链表 (opens new window)

给你链表的头节点 head ，每 k_ 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k _的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    tail := head
    for i := 0; i < k; i++ {
        //剩余数量小于k的话，则不需要反转。
        if (tail == nil) {
            return head;
        }
        tail = tail.Next;
    }

    // 反转前 k 个元素
    newHead := reverse(head, tail);
    //下一轮的开始的地方就是tail
    head.Next = reverseKGroup(tail, k);

    return newHead;
}

func reverse(head *ListNode, tail *ListNode) *ListNode {
    var pre *ListNode
    var next *ListNode
    for head != tail {
        next = head.Next;
        head.Next = pre;
        pre = head;
        head = next;
    }
    return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 两两交换链表中的节点 (opens new window)

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{
        Next: head,
    }
    //head=list[i]//pre=list[i-1]
    pre := dummy 
    for head != nil && head.Next != nil {
        pre.Next = head.Next
        next := head.Next.Next
        head.Next.Next = head
        head.Next = next
        //pre=list[(i+2)-1]
        pre = head 
        //head=list[(i+2)]
        head = next
    }
    return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n_ _个结点，并且返回链表的头结点。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummyNode := &ListNode{0, head}
	fast, slow := dummyNode, dummyNode
	for i := 0; i <= n; i++ { // 注意<=，否则快指针为空时，慢指针正好在倒数第n个上面
		fast = fast.Next
	}
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return dummyNode.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    l1,l2 := headA, headB
    for l1 != l2 {
        if l1 != nil {
            l1 = l1.Next
        } else {
            l1 = headB
        }

        if l2 != nil {
            l2 = l2.Next
        } else {
            l2 = headA
        }
    }

    return l1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 环形链表 II (opens new window)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 _如果链表无环，则返回 __null_

func detectCycle(head *ListNode) *ListNode {
    i, cur := 0, head
    m := map[*ListNode]*ListNode{}
    for cur != nil {
        if _, ok := m[cur]; ok {
            return m[cur]
        }
        m[cur] = cur
        i++
        cur = cur.Next
    }
    return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 树Tree

二叉树

# 迭代遍历

// 前序遍历
func preorderTraversal(root *TreeNode) []int {
    ans := []int{}

	if root == nil {
		return ans
	}

	st := []*TreeNode{root}

    for len(st) > 0 {
        node := st[len(st)-1]
        st = st[:len(st)-1]

        ans = append(ans, node.Val)
        if node.Right != nil {
            st = append(st, node.Right)
        }
        if node.Left != nil {
            st = append(st, node.Left)
        }
    }
    return ans
}

// 中序遍历
func inorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}
    for root!=nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, root.Val)
        root = root.Right
    }
    return res
}

//后续遍历
func postorderTraversal(root *TreeNode) []int {
	res := []int{}
	stk := []*TreeNode{}
	var prev *TreeNode

	for root != nil || len(stk) > 0 {
		for root != nil {
			stk = append(stk, root)
			root = root.Left
		}
        root = stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root
            root = nil
        } else {
            stk = append(stk, root)
            root = root.Right
        }
	}
	return res
}

//层序遍历
func levelOrder(root *TreeNode) (res [][]int) {
    if root == nil {
        return
    }

    curLevel := []*TreeNode{root}  // 存放当前层节点
    for len(curLevel) > 0 {
        nextLevel := []*TreeNode{}  // 准备通过当前层生成下一层
        vals := []int{}

        for _, node := range curLevel {
            vals = append(vals, node.Val) // 收集当前层的值
            // 收集下一层的节点
            if node.Left != nil {
                nextLevel = append(nextLevel, node.Left)
            }
            if node.Right != nil {
                nextLevel = append(nextLevel, node.Right)
            }
        }
        res = append(res, vals)
        curLevel = nextLevel // 将下一层变成当前层
    }
    return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

# 递归遍历

// 前序
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        res = append(res, node.Val)
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return res
}

// 中序
func postorderTraversal(root *TreeNode) (res []int) {
    var traversal func(node *TreeNode)
    traversal = func(node *TreeNode) {
    	if node == nil {
    	    return
    	}
    	traversal(node.Left)
    	res = append(res,node.Val)
        traversal(node.Right)
    }
    traversal(root)
    return res
}

// 后续
func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        dfs(node.Right)
        res = append(res, node.Val)
    }
    dfs(root)
    return res
}

// 层序
func levelOrder(root *TreeNode) [][]int {
	arr := [][]int{}

	depth := 0

	var order func(root *TreeNode, depth int)

	order = func(root *TreeNode, depth int) {
		if root == nil {
			return
		}
		if len(arr) == depth {
			arr = append(arr, []int{})
		}
		arr[depth] = append(arr[depth], root.Val)

		order(root.Left, depth+1)
		order(root.Right, depth+1)
	}

	order(root, depth)

	return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

# 二叉树构造

# 从中序、后序遍历序列构造 (opens new window)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder) == 0 {
        return nil
    }

    root := &TreeNode{postorder[len(postorder)-1], nil, nil}
    i:=0
    for ; i<len(inorder); i++ {
        if root.Val == inorder[i] {
            break
        }
    }
    root.Left = buildTree(inorder[:i], postorder[:len(inorder[:i])])
    root.Right = buildTree(inorder[i+1:], postorder[len(inorder[:i]):len(postorder)-1])
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 从前序、中序遍历序列构造 (opens new window)

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &TreeNode{preorder[0], nil, nil}
    i:=0
    for ;i<len(inorder); i++ {
        if preorder[0] == inorder[i] {
            break
        }
    }
    root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
    root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 二叉搜索树的插入 (opens new window)节点 (opens new window)

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。 回想一下：

  • 叶节点 是二叉树中没有子节点的节点
  • 树的根节点的 **深度 **为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
  • 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        root = &TreeNode{Val: val}
        return root
    }
    if root.Val > val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

//迭代法
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val:val}
    }
    node := root
    var pnode *TreeNode
    for node != nil {
        if val > node.Val {
            pnode = node
            node = node.Right
        } else {
            pnode = node
            node = node.Left
        }
    }
    if val > pnode.Val {
        pnode.Right = &TreeNode{Val: val}
    } else {
        pnode.Left = &TreeNode{Val: val}
    }
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 二叉搜索树的删除节点 (opens new window)

给定一个二叉搜索树的根节点 **root **和一个值 key，删除二叉搜索树中的 **key **对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if key < root.Val {
		root.Left = deleteNode(root.Left, key)
		return root
	}
	if key > root.Val {
		root.Right = deleteNode(root.Right, key)
		return root
	}
	if root.Right == nil {
		return root.Left
	}
	if root.Left == nil {
		return root.Right
	}
	minnode := root.Right
	for minnode.Left != nil {
		minnode = minnode.Left //找到右子树中的最小的数
	}
	root.Val = minnode.Val		//将右子树中最小的数复制给被删除节点
	root.Right = deleteNode1(root.Right) //删除右子树中最小的节点
	return root
}

func deleteNode1(root *TreeNode) *TreeNode {
	if root.Left == nil {
		pRight := root.Right //将被删除的节点的左节点本来就是nil, 右节点需要保留下来。
		root.Right = nil     //删除右子树中最小的节点
		return pRight
	}
	root.Left = deleteNode1(root.Left)
	return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 修剪二叉搜索树 (opens new window)

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

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

	root.Left = trimBST(root.Left, low, high)
	root.Right = trimBST(root.Right, low, high)

	return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 将有序数组转换为二叉搜索树 (opens new window)

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡二叉搜索树。

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	idx := len(nums) / 2
	root := &TreeNode{Val: nums[idx]}
	root.Left = sortedArrayToBST(nums[:idx])
	root.Right = sortedArrayToBST(nums[idx+1:])
	return root
}
1
2
3
4
5
6
7
8
9
10

# 红黑树

# AVL & 红黑树

# AVL树

平衡标准比较严格：每个左右子树的高度差不超过1 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28） 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整

# 红黑树

平衡标准比较宽松：没有一条路径会大于其他路径的2倍 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40） 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整

# 如何选择

搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树 相对于AVL树，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

# 其他类型

# 在二叉树中分配硬币 (opens new window)

给你一个有 n 个结点的二叉树的根结点 root ，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。 在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点，或者从子结点移动到父结点。 返回使每个结点上 只有 一枚硬币所需的 最少 移动次数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distributeCoins(root *TreeNode) int {
	var dfs func(node *TreeNode) (int, int)
	res := 0
	dfs = func(node *TreeNode) (int, int) {
		if node == nil {
			return 0, 0
		}
		coinL, nodeL := dfs(node.Left)
		coinR, nodeR := dfs(node.Right)
		conis := coinL + coinR + node.Val
		nodes := nodeL + nodeR + 1
		res += abs(conis, nodes)
		return conis, nodes
	}
	dfs(root)
	return res
}

func abs(x, y int) int {
	x = x - y
	if x < 0 {
		return -x
	}
	return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 跳表

image.png

编辑 (opens new window)
上次更新: 2024/09/13, 11:59:12
单调栈
前缀和-栈-队列-堆等数据结构

← 前缀和-栈-队列-堆等数据结构→

最近更新
01
ceph分布式存储-对象存储(RGW)搭建
10-27
02
ceph分布式存储-集群客户端连接
10-27
03
ceph分布式存储-管理crushmap
10-27
更多文章>
Theme by Vdoing