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

青旅半醒 2022-02-15 08:51 160阅读 0赞

参考链接：[https://blog.csdn.net/yuanliang861/article/details/84640069][https_blog.csdn.net_yuanliang861_article_details_84640069]

#### 运行结果： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]

# 题目： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 2]

# 解法一：中序遍历 #

很好理解，网上答案很多，不废话。

# 解法二：二分查找 #

#### 题目分析： ####

二叉搜索树特点：左孩子值小于根节点，根节点值小于右孩子，那么树中最小节点一定是根节点最左边孩子。

#### 思路： ####

1.  如果根节点的左子树数量为k-1，那么第k小的为根节点。
2.  如果根节点左子树的数量大于k-1，说明第k小的节点在左子树中，使用递归，查找其左子树。
3.  如果根节点左子树的数量小于k-1,说明第k小的节点在右子树中，使用递归，查找右子树。
    
    \-但是要查找的是在右子树中第\[k-根节点的左子树节点数-1\]小的节点。

# JAVA代码： #

/** * @author LaZY(李志一) * @create 2019-04-24 9:19 */
     class TreeNode{ 
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){ val = x;}
    }
    
    public class Solution { 
    
    
        /*** * 返回第k小的值。 * @param root * @param k * @return */
        public int kthSmallest(TreeNode root,int k){ 
            int count = calculate(root.left);
            if(count == k - 1){ return root.val;}
            if(count > k - 1){ return kthSmallest(root.left,k);}
    // if (count < k - 1){return kthSmallest(root.right,k - count - 1);}
            else { return kthSmallest(root.right,k - count - 1);}
        }
    
        /*** * 计算当前树中的节点个数=根节点 + 左子树节点数 + 右子树节点数 * @param root * @return 当前节点为根节点的树的所有节点的个数 */
        public int calculate(TreeNode root){ 
            if(root == null){ 
                return 0;
            }
            return 1 + calculate(root.left) + calculate(root.right);
        }
        
    }

github地址：[https://github.com/lazy-apple/LeetCode/blob/master/algorithm/src/alg230/Solution.java][https_github.com_lazy-apple_LeetCode_blob_master_algorithm_src_alg230_Solution.java]

[https_blog.csdn.net_yuanliang861_article_details_84640069]: https://blog.csdn.net/yuanliang861/article/details/84640069
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]: /images/20220215/c645c4e7177c4504a1721ac53b80c81f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 1]: /images/20220215/ec0489304af345d98959389da811b430.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 2]: /images/20220215/d428c9e9579f4d4f839c8b8d992d024b.png
[https_github.com_lazy-apple_LeetCode_blob_master_algorithm_src_alg230_Solution.java]: https://github.com/lazy-apple/LeetCode/blob/master/algorithm/src/alg230/Solution.java