題目描述

給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。

思路

這里先指明題目中蘊(yùn)含的一個(gè)特點(diǎn)，二叉搜索書的中序遍歷的順序就是從小到大的排序順序。
一個(gè)很簡(jiǎn)單的思路就是先把樹中序遍歷，然后取第k個(gè)值。
邊界情況要分別注意k過?。?）和過大（超過樹的大小）。
針對(duì)樹很大的情況，可以在每次向遍歷結(jié)果中加入節(jié)點(diǎn)時(shí)判斷一下是否是第k個(gè)?？梢蕴崆敖K止遍歷。

代碼

class Solution:
    # 返回對(duì)應(yīng)節(jié)點(diǎn)TreeNode
    def KthNode(self, pRoot, k):
        if k == 0:
            return None
        stack = []
        root = pRoot
        result = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            node = stack.pop()
            result.append(node)
            if len(result) == k: #如果樹很大，可以提前終止遍歷
                return node
            root =node.right
        if k>len(result):
            return None
        return result[k-1]