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

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

思路：
这道题目实际上是考二叉树的遍历，如果按照中序遍历，那么随即可以得出第k大的节点。可以用递归方式和非递归方式进行遍历。

代码实现一：

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        #特殊情况
        if not pRoot or k<=0:
            return None
        res = []
        def Inorder(pRoot):
            if pRoot == None:
                return []
            Inorder(pRoot.left)
            res.append(pRoot)
            Inorder(pRoot.right)
        
        Inorder(pRoot)
        if len(res)< k:
            return None
        return res[k-1]

代码实现二：

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        #特殊情况
        if not pRoot or k<=0:
            return None
        def inorder2(pRoot):
            if pRoot == None:
                return []
            sol = []
            stack = []
            node = pRoot
            while node or stack:
                #左子树压入栈
                while node:
                    stack.append(node)  #压入栈
                    node = node.left
                node = stack.pop()
                sol.append(node)
                node = node.right
            return sol
        res = inorder2(pRoot)
        if len(res) <k:
            return None
        return res[k-1]

提交结果：

非递归方式