面试题54：二叉搜索树的第k个节点

题目描述

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

知识点

二叉搜索树

Qiang的思路

因为二叉搜索树具有左子树节点小于根节点，右子树节点大于根节点的特点，所以当采取中序遍历的时候，得到的遍历序列是非递减的。此时，只要找的第k个值就是我们需要的结果。但是实际上我们并不需要得到完整的遍历序列，我们只需要遍历k个节点就能得到需要的结果。因为采取中序遍历时遍历到的第k个节点就是结果。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def getResult(self, pRoot, k):
        if pRoot.left!=None:
            node, k=self.getResult(pRoot.left, k)
            if node!=None:
                return node, k-1
        if k==1:
            return pRoot, k-1
        k-=1
        if pRoot.right!=None:
            node, k=self.getResult(pRoot.right, k)
            if node!=None:
                return node, k-1
        return None, k
    
    def KthNode(self, pRoot, k):
        # write code here
        if pRoot==None or k<1:
            return None
        node, k=self.getResult(pRoot, k)
        return node

这个题需要注意的是k的更新问题，没遍历完一个节点就需要对其做更新操作。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。