求一个二叉搜索树的第K小值

发表于 更新于 分类于
求一个二叉搜索树的第K小值

题目如下

  • 求一个二叉搜索树的第K小值

补充

  • 二叉树
    • 每个节点，最多只能有2个子节点
    • 树节点的数据结构 {value, left?,right?}
  • 二叉树的遍历
    • 前序遍历：root -> left -> right
    • 中序遍历：left -> root -> right
    • 后序遍历：left -> right -> root
  • 二叉搜索树 BST （Binary Search Tree）
    • left（包括其后代）value <= root value
    • Right（包括其后代）value >= root value
    • 可以使用二分法进行快速查找
  • 为什么二叉树如此重要，而不是三叉树、四叉树？
    • 性能，性能，还是性能
    • 数组：查找快O(1)，增删慢O(n)
    • 链表：查找慢O(n)，增删快O(1)
    • 二叉搜索树 BST：查找快，增删快—— “木桶效应”
    • 特定的二叉树（BBST）可以让整体效果最优
    • 各种高级的二叉树，继续优化，以满足不同场景

思路如下

  • BST中序遍历，即从大到小的排序
  • 找到排序后的第K值即可
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
/**
 * @description 二叉搜索树
 * @author sola-grj
 */

export interface ITreeNode {
    value: number
    left: ITreeNode | null
    right: ITreeNode | null
}

const arr: number[] = []

/**
 * 二叉树前序遍历
 * @param node tree node
*/
function preOrderTraverse(node: ITreeNode | null) {
  if(node == null) return
  arr.push(node.value)
  preOrderTraverse(node.left)
  preOrderTraverse(node.right)
}

/**
 * 二叉树中序遍历
 * @param node tree node
 */
function inOrderTraverse(node: ITreeNode | null) {
    if (node == null) return
    inOrderTraverse(node.left)
    // console.log(node.value)
    arr.push(node.value)
    inOrderTraverse(node.right)
}

/**
 * 二叉树后序遍历
 * @param node tree node
 */
function postOrderTraverse(node: ITreeNode | null) {
    if (node == null) return
    postOrderTraverse(node.left)
    postOrderTraverse(node.right)
    // console.log(node.value)
    arr.push(node.value)
}

/**
 * 寻找 BST 里的第 K 小值
 * @param node tree node
 * @param k 第几个值
 */
export function getKthValue(node: ITreeNode, k: number): number | null {
    inOrderTraverse(node)
    return arr[k - 1] || null
}
const bst: ITreeNode = {
    value: 5,
    left: {
        value: 3,
        left: {
            value: 2,
            left: null,
            right: null
        },
        right: {
            value: 4,
            left: null,
            right: null,
        }
    },
    right: {
        value: 7,
        left: {
            value: 6,
            left: null,
            right: null
        },
        right: {
            value: 8,
            left: null,
            right: null
        }
    }
}


单元测试

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
/**
 * @description 二叉搜索树 test
 * @author sola-grj
 */

import { ITreeNode, getKthValue } from './binary-search-tree'

describe('二叉搜索树', () => {
    const bst: ITreeNode = {
        value: 5,
        left: {
            value: 3,
            left: {
                value: 2,
                left: null,
                right: null
            },
            right: {
                value: 4,
                left: null,
                right: null,
            }
        },
        right: {
            value: 7,
            left: {
                value: 6,
                left: null,
                right: null
            },
            right: {
                value: 8,
                left: null,
                right: null
            }
        }
    }

    it('正常情况', () => {
        const res = getKthValue(bst, 3)
        expect(res).toBe(4)
    })

    it('k 不再正常范围之内', () => {
        const res1 = getKthValue(bst, 0)
        expect(res1).toBeNull()

        const res2 = getKthValue(bst, 1000)
        expect(res2).toBeNull()
    })
})