給定一個(gè)二叉搜索樹，編寫一個(gè)函數(shù) kthSmallest 來查找其中第 k 個(gè)最小的元素。說明： 你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個(gè)數(shù)。示例 1:輸入: root = [3,1,4,null,2], k = 13/ \1 4\2 輸出: 1

解題思路

變量 cnt:統(tǒng)計(jì)已經(jīng)按序遍歷多少個(gè)節(jié)點(diǎn)了
變量 r： 記錄 第 k 個(gè)最小元素的值

根據(jù)二叉搜索樹中序遍歷的性質(zhì)，我們可以按二叉樹節(jié)點(diǎn)大小訪問二叉樹，記錄下第k個(gè)遍歷的節(jié)點(diǎn)，就是我們需要找到的第 k 個(gè)最小元素

代碼

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/ class Solution {int r = -1;int cnt = 0;public int kthSmallest(TreeNode root, int k) {mid(root, k);return r;}public void mid(TreeNode root, int k) {if (root == null) return;mid(root.left, k);if (++cnt == k)r = root.val;mid(root.right, k);} }

總結(jié)

以上是生活随笔為你收集整理的leetcode230. 二叉搜索树中第K小的元素（中序遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。