二叉搜索树第K小元素

1.思路：迭代法

计算出二叉树左节点的个数，如果左节点的个数等于k-1;则根节点就是我们要找的值，如果左节点的个数大于k-1，表明我们要查找的第k个最小元素在左子树中，如果左节点的个数小于k-1，表明要查找的第k个最小元素在右子节点中，找到右子树中第k-count(left)-1个元素就是我们要找的元素

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        /*
        迭代
        */
        int leftcon=count(root.left);
        if(leftcon==k-1) return root.val;
        if(leftcon>k-1) return  kthSmallest(root.left, k);
        return  kthSmallest( root.right, k-leftcon-1);
    }
    public int count(TreeNode root){
        if(root==null) return 0;
        return 1+count(root.left)+count(root.right);
    }
}

2.中序遍历；中序遍历二叉搜索树，排序是一个从小到大的数组

class Solution {
    private int cnt=0;
    private int val;
    public int kthSmallest(TreeNode root, int k) {
       //中序遍历
        inOrder(root,k);
        return val;
}
    public void inOrder(TreeNode node,int k){
        if(node==null) return;
        inOrder(node.left,k);
        cnt++;
        if(cnt==k){
            val=node.val;
            return;
        }
        inOrder(node.right,k);
    }
}

最后

以上就是潇洒纸鹤为你收集整理的二叉搜索树第K小元素的全部内容，希望文章能够帮你解决二叉搜索树第K小元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。