剑指62-二叉搜索树的第k个结点

Posted on | In |

题目描述

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

输入的是根节点，要求返回节点。

  • 中序遍历二叉搜索树，输出序列是非递减序列。如下代码用了递归中序遍历，递归函数是返回的节点或者None。
  • 用pt来记录得到结果要再访问的节点数，每访问一个节点，值减去1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        def recur(root, pt):
            if root.left is not None:
                res_l = recur(root.left, pt)
                if res_l:
                    return res_l
            if pt[0] == 1:
                return root
            pt[0] -= 1
            if root.right is not None:
                res_r = recur(root.right, pt)
                if res_r:
                    return res_r
            return None
            
        pt = [k]
        if pRoot is None or k <= 0:
            return None
        return recur(pRoot, pt)