【每日一题】LeetCode 230. 二叉搜索树中第 K 小的元素 TypeScript

给定一个二叉搜索树的根节点root和一个整数k请你设计一个算法查找其中第k小的元素k从 1 开始计数。示例 1输入root [3,1,4,null,2], k 1输出1示例 2输入root [5,3,6,2,4,null,null,1], k 3输出3提示树中的节点数为n。1 k n 1040 Node.val 104注意二叉搜索树是指满足 左节点根节点右节点 的二叉树所以可以通过中序遍历给二叉树“排序”按升序遍历二叉树第k个小的元素就是“升序遍历”的第k个位置的值/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */ function kthSmallest(root: TreeNode | null, k: number): number { let count 0 let result 0 const inorder (node:TreeNode | null ):void { if(!node || countk) return inorder(node.left) count if(countk){ result node.val return } inorder(node.right) } inorder(root) return result };/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */ function kthSmallest(root: TreeNode | null, k: number): number { //count是计数器指遍历到了哪一位 let count 0 //result存放符合条件的val值 let result 0 const inorder (node:TreeNode | null ):void { if(!node || countk) return inorder(node.left) count if(countk){ result node.val return } inorder(node.right) } inorder(root) return result };共勉