Fork me on GitHub

11. 二叉树-DFS (迭代)

0 - 算法, 0.0 - 算法模版

正文

先序遍历（写法一）

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
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun preorderTraversal(root: TreeNode?) {
    val stack = LinkedList<TreeNode>()
    root ?: return
    stack.addFirst(root)

    while (!stack.isEmpty()) {
        val current = stack.removeFirst()
        visit(current)
        
        // 先将右子节点入栈，再将左子节点入栈
        if (current.right != null) {
            stack.addFirst(current.right)
        }
        if (current.left != null) {
            stack.addFirst(current.left)
        }
    }
}

fun visit(root: TreeNode){
    println(root.value)
}

先序遍历（写法二）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun preorderTraversal(root: TreeNode?) {
    val stack = LinkedList<TreeNode>();
    var cur: TreeNode = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            visit(cur)
            stack.addFirst(cur);
            cur = cur.left;
        }

        val top: TreeNode = stack.removeFirst(();
        cur = top.right;
    }
}

fun visit(node: TreeNode){
    println(node.value)
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorderTraversal(root: TreeNode?) {
    val stack = LinkedList<TreeNode>();
    var cur: TreeNode = root;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.addFirst(cur);
            cur = cur.left;
        }

        visit(cur)
        val top: TreeNode = stack.removeFirst(();
        cur = top.right;
    }
}

fun visit(node: TreeNode){
    println(node.value)
}

后序遍历

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
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun postorder(root: TreeNode?) {
    val stack: LinkList = LinkedList<TreeNode>()
    var cur = root
    var last = null
    
    while (cur != null || !stack.isEmpty()) {
        // 左节点先入栈
        while (cur != null) { 
            stack.addFirst(cur)                        // 第一次访问
            cur = cur.left
        }
        val top = stack.peekFirst()                    // 第二次访问
        if (top.right == null || top.right == last) {  // 第三次访问
            visit(top)
            last = top
            stack.removeFirst()
        } else {
            cur = top.right
        }
    }
}

fun visit(node: TreeNode){
    println(node.value)
}

非递归后续遍历比较有意思
结合注释我们来一语道破天机
先序，中序，后序遍历
第一次经过结点（从双亲过来）: 先序
第二次经过结点（从左孩子过来）: 中序
第三次经过结点（右孩子过来）: 后序

12. 二叉树-BFS

0 - 算法, 0.0 - 算法模版

正文

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
import java.util.LinkedList

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun bfs(root: TreeNode?) {
    val queue: LinkedList<TreeNode> = LinkedList()
    queue.add(root)
    
    while (!queue.isEmpty()) {
        val node: TreeNode = queue.removeFirst()
        visit(node)

        if (node.left != null) {
            queue.add(node.left)
        }
        if (node.right != null) {
            queue.add(node.right)
        }
    }
}

fun visit(root: TreeNode){
    println(root.value)
}

13. 图-DFS (递归)

0 - 算法, 0.0 - 算法模版

正文

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
class Graph {
    private val adjList: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    fun addEdge(u: Int, v: Int) {
        adjList.getOrPut(u) { mutableListOf() }.add(v)
    }

    fun dfs(vertex: Int) {
        val visited = mutableSetOf<Int>()
        dfsHelper(vertex, visited)
    }

    private fun dfsHelper(vertex: Int, visited: MutableSet<Int>) {
        visited.add(vertex)
        println(vertex) // 在这里可以对当前节点进行相关操作

        val neighbors = adjList[vertex]
        if (neighbors != null) {
            for (neighbor in neighbors) {
                if (!visited.contains(neighbor)) {
                    dfsHelper(neighbor, visited)
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()
    // 添加图的边
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    graph.addEdge(3, 4)

    // 从节点 0 开始进行深度优先搜索
    graph.dfs(0)
}

14. 图-DFS (迭代)

0 - 算法, 0.0 - 算法模版

正文

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
class Graph {
    private val adjacencyList: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    fun addEdge(u: Int, v: Int) {
        adjacencyList.computeIfAbsent(u) { mutableListOf() }.add(v)
    }

    fun dfs(start: Int) {
        val visited = mutableSetOf<Int>()
        val stack = mutableListOf<Int>()

        stack.add(start)
        while (stack.isNotEmpty()) {
            val vertex = stack.removeAt(stack.size - 1)
            if (!visited.contains(vertex)) {
                visited.add(vertex)
                println("Visited vertex: $vertex")

                adjacencyList[vertex]?.reversed()?.forEach { neighbor ->
                    if (!visited.contains(neighbor)) {
                        stack.add(neighbor)
                    }
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()

    // 添加图的边
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 5)
    graph.addEdge(2, 6)

    // 从顶点0开始进行DFS
    graph.dfs(0)
}

15. 图-BFS

0 - 算法, 0.0 - 算法模版

正文

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
import java.util.*

class Graph {
    private val adjacencyList: MutableMap<Int, MutableList<Int>> = HashMap()

    fun addEdge(src: Int, dest: Int) {
        adjacencyList.computeIfAbsent(src) { mutableListOf() }.add(dest)
        adjacencyList.computeIfAbsent(dest) { mutableListOf() }
    }

    fun bfs(startVertex: Int) {
        val visited = BooleanArray(adjacencyList.size)
        val queue: Queue<Int> = LinkedList()

        visited[startVertex] = true
        queue.offer(startVertex)

        while (!queue.isEmpty()) {
            val currentVertex = queue.poll()
            print("$currentVertex ")

            val neighbors = adjacencyList[currentVertex]
            if (neighbors != null) {
                for (neighbor in neighbors) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true
                        queue.offer(neighbor)
                    }
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)

    println("BFS traversal starting from vertex 2:")
    graph.bfs(2)
}

18. 二分查找-重复元素，最左边的插入点

0 - 算法, 0.0 - 算法模版

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2

        if (nums[mid] == target) {
            // 找到了目标元素，返回索引
            return mid
        } else if (nums[mid] < target) {
            // 目标元素在右半部分，更新左边界
            left = mid + 1
        } else {
            // 目标元素在左半部分，更新右边界
            right = mid - 1
        }
    }

    // 目标元素不存在，返回插入位置
    return left
}

19. 二分查找-重复元素，最右边的插入点

0 - 算法, 0.0 - 算法模版

正文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    var result = nums.size // 默认插入到最右边

    while (left <= right) {
        val mid = left + (right - left) / 2

        if (nums[mid] <= target) {
            if (nums[mid] == target) {
                // 找到目标元素，更新结果为当前索引
                result = mid
            }
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return result
}