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

Posted on |

二叉搜索树的第k个结点

题目

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

方法

类似于Leetcode 230. 二叉搜索树中的第k小元素，与本题目的不同之处在于k不能保证是有效的，且返回的是结点，而不是结点的元素值。

无效的情况：

  • 二叉树是空树
  • $k \leq 0$
  • $k>nums_of_nodes_in_tree$

左子树的所有结点的数值都小于root，右子树的所有结点的数值都大于root。即，当k刚好等于左结点数量+1，那么第k小的元素刚好是root的数值。
否则的话，递归调用主函数，在根结点的左子树或右子树继续进行搜索。

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def countNodes(self,root):
        if root is None:
            return 0
        else:
            return 1+self.countNodes(root.left)+self.countNodes(root.right)
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot or not k:
            return None

        # 根结点的左子树的结点数量
        leftCount=self.countNodes(pRoot.left)
        if k<=leftCount:
            return self.KthNode(pRoot.left,k)
        elif k==leftCount+1:
            return pRoot
        else:
            return self.KthNode(pRoot.right,k-1-leftCount)
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
# -*- 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 not pRoot or not k:
            return

        self.res=[]
        self.inorder(pRoot)
        if k>len(self.res):
            return
        else:
            return self.res[k-1]

    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)
        self.res.append(root)
        self.inorder(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- 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 not pRoot or k<=0:
            return
        res=self.inorder(pRoot)
        if len(res)<k:
            return
        else:
            return res[k-1]
    def inorder(self,root):
        if not root:
            return []
        return self.inorder(root.left)+[root]+self.inorder(root.right)