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

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

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

为什么要用中序遍历：

看到二叉搜索树，应该会立刻想到它的一个性质，它的中序遍历输出的是一个升序数组。知道了这个，这道题就很简单了，只需要把中序遍历的第 k 个元素返回即可==> 我们要找第k个，就是从小到大排k-1个！

给一个二叉搜索树，找到树中第 k 小的树。二叉搜索树的定义如下：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

//递归dfs，中序遍历，套模板，返回不是整个🌲，而是树的k-1个
func kthSmallest(root *TreeNode, k int) int {
    res := []int{}          //暂存一个数组，存二叉树
    inerder(root, &res)     //递归函数，参数父节点，遍历的值
    return res[k-1]         //返回结果,中序的左中右，单调递增的
}
func inerder(root *TreeNode, res *[]int) {
    if root == nil {            //终止条件，根节点为空
        return 
    }
    inerder(root.Left, res)     //中序遍历，前中后子树，核心三句
    *res = append(*res, root.Val)
    inerder(root.Right, res)
}

//2.迭代
func kthSmallest(root *TreeNode, k int) int {
    //1,二叉树初始赋值，定义栈是二叉树结构，res是数组结构
    stack := []*TreeNode{}
    res := []int{}

    //2,一直找到最底层 的左节点
    for root != nil || len(stack) >0 {
        for root != nil {               //结束遍历条件，父节点为空
            stack = append(stack,root)  //存进所以父节点，层层放置
            root = root.Left            //走最左路径
        }

        //3,弹出栈，模拟递归过程
        root = stack[len(stack)-1]      //向上回溯父节点，核心四句
        stack = stack[:len(stack)-1]    //栈的深度减一
        res = append(res,root.Val)      //左中右，存储进res数组里，遍历的节点值
        root = root.Right               //拿到右节点
    }

    return res[k-1]                        //核心：返回不是整个🌲，只要第k-1个就行
}

分治算法：不使用中序遍历，速度快，内存消耗小

我们只需要先计算左子树的节点个数，记为 n，然后有三种情况。
n + 1 == k，那就说明当前根节点就是我们要找的。
n + 1 < k，那就说明第 k 小的数一定在右子树中，我们只需要递归的在右子树中寻找第 k - (n + 1) 小的数即可。
n + 1 > k，那就说明第 k 小个数一定在左子树中，我们只需要递归的在左子树中寻找第 k 小的数即可。

//分治法，高级货色
func kthSmallest(root *TreeNode, k int) int {
    if root == nil {
        return 0
    }

    n := countNodes(root.Left)
    if n + 1 == k {
        return root.Val                            // 如果是根节点
    }

    if n + 1 < k {
        return kthSmallest(root.Right, k-n-1)    // 如果左子树的节点不够k，那么搜索右边的子树
    }
    return kthSmallest(root.Left, k)
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    // 1 for root
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}