TS数据结构与算法之获二叉搜索树第K小值

二叉搜索树BST（Binary Search Tree）

特点

• left(包括其后代) value <= root value
• right(包括其后代) value >= root value
• 可使用二分法进行快速查找

        5
      /   \
    3      7
   / \     /\
  2   4   6  8

解题思路

• BST 中序遍历，即从小到大的排序
• 找到排序后的第K值即可

代码演示

import {
  TreeNode,
  inOrderTraverse,
} from './binary-tree-iterator';

/**
 * 求二叉搜索树第K小值
 * @param node 待搜索的二叉查找树
 * @param k 第K项值
 * @returns 返回找到的项或未找到
 */
export function getKthValue (
  node: TreeNode,
  k: number
): number | undefined {
  const arr: number[] = [];

  // 中序遍历
  inOrderTraverse(node, (item: number) => {
    arr.push(item);
  });

  return arr?.[k - 1];
}

功能测试

export function getKthValueFunctionalTest() {
  // nst 是提前定义好的 中序如下的二叉搜索树
  // [2, 3, 4, 5, 6, 7, 8]
  const arr: number[] = [];
  const val = getKthValue(nst, 3); 
  console.log('val', val); // 4
}

单元测试

/**
 * 二叉搜索树获取第K小值
 */
 import { TreeNode } from '../src/utils/binary-tree-iterator';
 import { getKthValue } from '../src/utils/binary-search-tree';

describe('获取二叉搜索树第K小值单元调试', () => {
  // 定义二叉搜索树 中序遍历是：[2, 3, 4, 5, 6, 7, 8]
  const nst: TreeNode = {
    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('第3项应该是4', () => {
    const val = getKthValue(nst, 3);
    expect(val).toBe(4);
  });

  it('第100项应该是undefined', () => {
    const val = getKthValue(nst, 100);
    expect(val).toBeUndefined();
  });

  it('第1项应该是2', () => {
    const val = getKthValue(nst, 1);
    expect(val).toBe(2);
  });
});

测试输出：

 PASS  tests/binary-search-tree.test.ts
  获取二叉搜索树第K小值单元调试
    √ 第3项应该是4 (2 ms)
    √ 第100项应该是undefined
    √ 第1项应该是2 (1 ms)