1 """
 2 Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
 3 Note:
 4 You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
 5 Example 1:
 6 Input: root = [3,1,4,null,2], k = 1
 7    3
 8   / \
 9  1   4
10   \
11    2
12 Output: 1
13 Example 2:
14 Input: root = [5,3,6,2,4,null,null,1], k = 3
15        5
16       / \
17      3   6
18     / \
19    2   4
20   /
21  1
22 Output: 3
23 """
24 """
25 用栈中序遍历，加一条判断语句
26 if len(res) == k
27 """
28 # Definition for a binary tree node.
29 # class TreeNode:
30 #     def __init__(self, x):
31 #         self.val = x
32 #         self.left = None
33 #         self.right = None
34 
35 class Solution:
36     def kthSmallest(self, root, k):
37         stack = []
38         res = []
39         cur = root
40         while stack or cur:
41             if cur:
42                 stack.append(cur)
43                 cur = cur.left
44             else:
45                 cur = stack.pop()
46                 res.append(cur.val)
47                 if len(res) == k:  #中序遍历,中间加一个判断语句
48                     return res[-1]
49                 cur = cur.right