重庆网站建设网站,wordpress生成app插件,网站建设公司问候语,找个男做那个视频网站好二叉搜索树中第K小的元素
二叉搜索树具有如下性质#xff1a; 结点的左子树只包含小于当前结点的数。 结点的右子树只包含大于当前结点的数。 所有左子树和右子树自身必须也是二叉搜索树。
二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树#x…二叉搜索树中第K小的元素
二叉搜索树具有如下性质 结点的左子树只包含小于当前结点的数。 结点的右子树只包含大于当前结点的数。 所有左子树和右子树自身必须也是二叉搜索树。
二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树在访问其左子树和右子树时我们也按照同样的方式遍历直到遍历完整棵树。
因为二叉搜索树和中序遍历的性质所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是我们可以通过中序遍历找到第 k 个最小元素。
public class Solution {public int KthSmallest(TreeNode root, int k) {Listint res new Listint();StackTreeNode stack new StackTreeNode();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];}
}
