第93题求一个二叉搜索树的第k小值

二叉树

二叉树是一棵树
二叉树每个节点最多只能有两个子节点
树节点的数据结构{value,left?,right?}
二叉树的遍历
- 前序遍历：root => left => right
- 中序遍历：left => root => right
- 后序遍历：left => right => root
二叉搜索树BST(Binary Search Tree)的特点
- left（包含其后代）value <= root value
- right（包含其后代）value >= root value
- 二叉搜索树的价值可以让我们使用二分法 快速查找

思路分析

二叉搜索树中序遍历 ，即从小到大的排序
找到排序后的第k值即可

    /**
     * @description 二叉搜索树
     */
    
    // 数据结构
    interface ITreeNode {
      value: number
      left: ITreeNode | null
      right: ITreeNode | null
    }
    
    const arr = []
    
    /**
     * 二叉树前序遍历
     * @param node:ITreeNode tree node
     */
    function preOrderTraverse(node) {
      if (node == null) return
      // console.log(node.value)
      arr.push(node.value)
      preOrderTraverse(node.left)
      preOrderTraverse(node.right)
    }
    
    /**
     * 二叉树中序遍历
     * @param node:ITreeNode tree node
     */
    function inOrderTraverse(node) {
      if (node == null) return
      inOrderTraverse(node.left)
      // console.log(node.value)
      arr.push(node.value)
      inOrderTraverse(node.right)
    }
    
    /**
     * 二叉树后序遍历
     * @param node:ITreeNode tree node
     */
    function postOrderTraverse(node) {
      if (node == null) return
      postOrderTraverse(node.left)
      postOrderTraverse(node.right)
      // console.log(node.value)
      arr.push(node.value)
    }
    
    /**
     * 寻找 BST 里的第 K 小值
     * @param node tree node：ITreeNode
     * @param k:number 第几个值
     */
    function getKthValue(node, k) {
      inOrderTraverse(node) // 中序遍历
      // arr => [2, 3, 4, 5, 6, 7, 8]
      // k - 1从0开始
      return arr[k - 1] || null
    }

前序遍历（根左右）：5324768
中序遍历（左根右）：2345678
后序遍历（左右根）：2436875

    // 测试
    const bst = {
        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
            }
        }
    }
    
    // preOrderTraverse(bst)
    // inOrderTraverse(bst)
    // postOrderTraverse(bst)
    
    console.log(getKthValue(bst, 3)) // 4