[LeetCode] 230. Kth Smallest Element in a BST

轉自LeetCode

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

<Solution>

想法如下

• 因為 BST 的特性，用 inorder 歷遍的話，數字剛好會是從最小到最大

• 檢查目前的節點，是不是剛好就是指定的第 k 個

code 如下

Java(參考解答)

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	private int cnt;
	private int ans;
	public int kthSmallest(TreeNode root, int k) {
	cnt = k;
	inorder(root);
	return ans;
	}
	private void inorder(TreeNode root) {
	if(root == null) {
	return;
	}
	inorder(root.left);
	--cnt;
	if(cnt == 0) {
	ans = root.val;
	return;
	}
	inorder(root.right);
	}
	}

view raw kthSmallestInBST.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun kthSmallest(root: TreeNode?, k: Int): Int {
	val stack = mutableListOf<TreeNode>()
	var curN = root
	var cnt = 0
	while(stack.isNotEmpty() || curN != null) {
	while(curN != null) {
	stack.add(curN!!)
	curN = curN!!.left
	}
	curN = stack.last()
	++cnt
	if(cnt == k) {
	return curN!!.`val`
	}
	stack.removeAt(stack.lastIndex)
	curN = curN!!.right
	}
	return -1
	}
	}

view raw kth_smallest_element_in_a_BST.kt hosted with ❤ by GitHub