LeetCode [中等] 二叉树中序—二叉搜索树中第K小的元素
二叉搜索树中第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];
}
}