剑指offer 54：二叉搜索树中第K小的元素

剑指offer 54

题目：

二叉搜索树重要性质：BST的中序遍历是升序排列 ！
递归三部曲：
1.参数root和k，不需要返回值，改变成员变量rank和结果r就行
2.终止条件null则return
3.判断当前rank是否等于k

import java.util.*;
public class Solution {
    int rank=0;
    int r=-1;
    public int KthNode (TreeNode root, int k) { 
        // 中序是升序排列
        check(root,k);
        return r;
        
    }
    
    void check(TreeNode root,int k){
        if(root==null || k<=0 ){ 
        return;
    }
        check(root.left,k);
        // 中序
        rank++;
        if(rank==k){
            r=root.val;
            return;
        }
        check(root.right,k);
    }
}
    

时间复杂度：O(H+k)，其中 H 是树的高度，最小值 O(logN+k)，最大值 O(N+k)

当k<=0时，在终止条件中判定并return， 当k大于节点个数时，会遍历到null为止，并不会进入if(rank==k){...} ，所以r值并没有改变，返回 r= -1

方法一中，之所以需要中序遍历前 k 个元素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。
找到第 k 小的元素，或者说找到排名为 k 的元素，如果想达到对数级复杂度，关键也在于每个节点得知道他自己排第几。
这样就可以将搜索的时间复杂度降到 O(logN) 了。

那么，如何让每一个节点知道自己的排名呢？
每个节点需要记录，以自己为根的这棵二叉树有多少个子节点。
在实现中，可以将以每个结点为根结点的子树的结点个数存储在哈希表中or 使个数作为节点的属性之一。

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        MyBst bst = new MyBst(root);
        return bst.kthSmallest(k);
    }
}

class MyBst {
    TreeNode root;
    Map nodeNum;

    public MyBst(TreeNode root) {
        this.root = root;
        this.nodeNum = new HashMap();
        countNodeNum(root);
    }

    // 返回二叉搜索树中第k小的元素
    public int kthSmallest(int k) {
        TreeNode node = root;
        while (node != null) {
            int left = getNodeNum(node.left);
            if (left < k - 1) {
                node = node.right;
                k -= left + 1;
            } else if (left == k - 1) {
                break;
            } else {
                node = node.left;
            }
        }
        return node.val;
    }

    // 统计以node为根结点的子树的结点数
    private int countNodeNum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        nodeNum.put(node, 1 + countNodeNum(node.left) + countNodeNum(node.right));
        return nodeNum.get(node);
    }

    // 获取以node为根结点的子树的结点数
    private int getNodeNum(TreeNode node) {
        return nodeNum.getOrDefault(node, 0);
    }
}