题解 | #二叉搜索树的第k个结点#

第一想法很简单，就是学习前面“之”字型的方式，用一个 stack[] 把所有二叉树的Node按顺序从左到右收集起来,然后保存在，每次pop()一个node保存在res[]里，然后遍历res[]得到node的value值保存在res_value[]里，

然后使用sort()排序，最后返回指定第K个值对应的value所对应的node

#不过要注意K=0，pROOT = None，K>len(二叉树节点) 三种特殊情况返回None

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if k == 0 or pRoot == None:
            return None
        else:
            stack = [pRoot]
            res = []
            res_value = []
            while stack:
                node = stack.pop(0)#pop()默认是index = -1返回最后一个，也可以返回最前一个，此处就需要
                if node != None:
                    res.append(node) #res按顺序保存了所有从上到下，从左到右的Node
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            for i in res:
                res_value.append(i.val)
            res_value.sort()#res_final按从小到大保存了所有val
            if k >= len(res_value)+1:#如果K的值大于本身二叉树所有节点的数量则返回空
                return None
            for j in res:#
                if j.val == res_value[k-1]:
                    return j