leetcode-kth-smallest-bst

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/kth-smallest-element-in-a-bst/

　　给你一棵二叉查找树，输出第k小的元素

题目分析

　　中序遍历输出第k个元素即可。但这个题目还有扩展，当二叉树节点频繁增加删除时，还用这一思路复杂度高。因此如果可以更改数据结构的话，加个域，代表左边子树的节点个数，这样就可以在遍历每个节点时，就可以按照k和左边子树节点个数关系进行分路，复杂度会降到O(height of tree)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    private static int num = 0;
    private static int res;
    
    private void inOrder(TreeNode root, int k) {
        if(root == null) {
            return ;
        }
        if(num >= k) {
            return ;
        }
        inOrder(root.left, k);
        num++;
        if(num == k) {
            res = root.val;
            return ;
        }
        inOrder(root.right, k);
    }
    
    public int kthSmallest(TreeNode root, int k) {
        num = 0;
        inOrder(root, k);
        return res;
    }
}