二叉搜索树的第k个结点

1. 题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

2. 思路

• 中序遍历

3. 代码

3.1. 中序遍历

• java

public class 二叉搜索树的第k个结点
{
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        //判断参数是否合法
        if (pRoot == null || k <= 0)
        {
            return null;
        }
        //中序遍历生成有序list
        List<TreeNode> list = new LinkedList<>();
        this.midOrder(list, pRoot);
        //取出第k个
        if (list.size() < k)
        {
            return null;
        }
        return list.get(k-1);
    }


    private void midOrder(List<TreeNode> list, TreeNode pRoot)
    {
        if (pRoot.left != null)
        {
            this.midOrder(list, pRoot.left);
        }

        list.add(pRoot);

        if (pRoot.right != null)
        {
            this.midOrder(list, pRoot.right);
        }
    }
}

• go

//时间：O(N)
//空间：O(N)
func KthNode(pRoot *TreeNode, k int) *TreeNode {
	if pRoot == nil || k <= 0 {
		return nil
	}

	orders := make([]*TreeNode, 0)
	midOrderKthNode(pRoot, &orders)
	if len(orders) < k {
		return nil

	}
	return orders[k-1]
}

func midOrderKthNode(root *TreeNode, nodes *[]*TreeNode) {
	if root == nil {
		return
	}

	midOrderKthNode(root.Left, nodes)
	*nodes = append(*nodes, root)
	midOrderKthNode(root.Right, nodes)

}



//时间：O(N)
//空间：O(h)
func KthNode2(pRoot *TreeNode, k int) *TreeNode {
	if pRoot == nil || k <= 0 {
		return nil
	}

	current := 0
	return kthNode(pRoot, &current, k)
}

func kthNode(n *TreeNode, current *int, k int) *TreeNode {
	if n == nil {
		return nil
	}
	if node := kthNode(n.Left, current, k); node != nil {
		return node
	}
	*current = *current + 1
	if *current == k {
		return n
	}
	if node := kthNode(n.Right, current, k); node != nil {
		return node
	}
	return nil
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargest(root *TreeNode, k int) int {
    if root == nil || k <= 0 { return 0 }
    count := 0
    if node := kthLargestDFS(root, k, &count); node != nil {
        return node.Val
    }
    return 0
}

func kthLargestDFS(root *TreeNode, k int, count *int) *TreeNode {
    if root == nil || k <= 0 {return nil}
    if node := kthLargestDFS(root.Right, k, count); node != nil {
        return node
    }
    (*count)++
    if *count == k {
        return root
    }
    if node := kthLargestDFS(root.Left, k, count); node != nil {
        return node
    }
    return nil
}

4. 参考

• 二叉搜索树的第k个结点_牛客题霸_牛客网
• 剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）
• Kth Smallest Element in a BST - LeetCode