leetcode

Kth Smallest Element in a BST

Kth Smallest Element in a BST

中序遍历(In-Order Traversal)

指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

Iteratively 非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        ret = []
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return ret[k - 1]
            node = stack.pop()
            ret.append(node.val)
            root = node.right

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1
In [1]: class TreeNode(object):
   ...:     def __init__(self, x):
   ...:         self.val = x
   ...:         self.left = None
   ...:         self.right = None
   ...:
In [2]: one = TreeNode(1)
In [3]: two = TreeNode(2)
In [4]: one.right = two
In [5]: four = TreeNode(4)
In [6]: three = TreeNode(3)
In [7]: three.left = one
In [8]: three.right = four

result

1
2
In [21]: s = Solution(); s.kthSmallest(three, 1)
Out[21]: 1

BST二叉搜索树

leet code