二叉搜索树中第K小的元素

二叉搜索树具有如下性质：

• 结点的左子树只包含小于当前结点的数。

• 结点的右子树只包含大于当前结点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树；在访问其左子树和右子树时，我们也按照同样的方式遍历；直到遍历完整棵树。

因为二叉搜索树和中序遍历的性质，所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是，我们可以通过中序遍历找到第 k 个最小元素。

public class Solution {public int KthSmallest(TreeNode root, int k) {List<int> res = new List<int>();Stack<TreeNode> stack = new Stack<TreeNode>();while(stack.Count > 0 || root != null){while(root != null){stack.Push(root);root = root.left;}root = stack.Pop();res.Add(root.val);root = root.right;}return res[k - 1];}
}