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
3
/ 1 4
2
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ 3 6
/ 2 4
/
1
Output: 3
二叉搜索树的第k小节点
java:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public int kthSmallest(TreeNode root, int k) { 12 Stack<TreeNode> stack = new Stack<TreeNode>() ; 13 TreeNode cur = root ; 14 while(cur != null || !stack.isEmpty()){ 15 while(cur != null){ 16 stack.push(cur) ; 17 cur = cur.left ; 18 } 19 TreeNode node = stack.pop() ; 20 if (--k == 0){ 21 return node.val ; 22 } 23 cur = node.right ; 24 } 25 return 0 ; 26 } 27 }
230. Kth Smallest Element in a BST
原文：https://www.cnblogs.com/mengchunchen/p/10630987.html