二叉搜索树的第k个结点

题目描述

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

思路

1. 首先简单总结下二叉搜索树的性质。

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

2. 从二叉搜索树的性质可以看出，其中序遍历便是一个从小到大的排序。
3. 设置一个count，每遍历一个数据便自增1，当count=k时，就找到了正确答案。

Java代码实现

 public class Solution {
    TreeNode KthNode(TreeNode root, int k)
    {
        int count = 1;
        Stack<TreeNode> nodeList = new Stack<>();

        while(root != null || nodeList.size()>0){
            while(root != null){
                nodeList.push(root);
                root = root.left;
            }
            root = nodeList.pop();
            if(count == k){
                return root;
            }
            root = root.right;
            count++;
        }
        return null;
    }
}

Golang代码实现

func KthNode(root *TreeNode, k int) int {
    count := 1
    nodeList := list.New()
    for root != nil || nodeList.Len() > 0 {
        for root != nil {
            nodeList.PushFront(root)
            root = root.Left
        }
        root = nodeList.Front().Value.(*TreeNode)
        nodeList.Remove(nodeList.Front())
        if count == k {
            return root.Val
        }
        root = root.Right
        count++
    }
    return -1
}