剣指offer(二叉探索木のk番目の接点)-python 2実現と解析

タイトルの説明:
二叉探索木を1本与えて、その中のk番目の小さなノードを見つけてください.たとえば、(5,3,7,2,4,6,8)では、3番目に小さいノードの値がノードの数値の大きさ順に4となります.
牛客网
コード実装(python 2)

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    #       TreeNode
    flag = 0
    def KthNode(self, pRoot, k):
        # write code here
        node_list = []
        def middle_sort(pRoot,k):
            if not pRoot:
                return
            middle_sort(pRoot.left,k)
            node_list.append(pRoot)
            self.flag += 1
            if self.flag == k:
                return
            middle_sort(pRoot.right,k)
        middle_sort(pRoot,k)
        return node_list[k-1] if 0<k<=len(node_list) else None

テーマ解析
二叉探索ツリー(BST:Binary Search Tree)は、二叉探索ツリーとも呼ばれる.ツリーノードの検索効率を向上させる特殊なツリーです.二叉ルックアップツリーには、任意のノードnについて、左サブツリー(left subtree)の各子孫ノード(descendant node)の値がノードnの値よりも小さい性質がある.その右サブツリー(right subtree)の下の各子孫ノードの値は、ノードnの値よりも大きい.二叉探索ツリーの性質から,二叉探索ツリーが中順に遍歴する順序で印刷されるのがちょうど並べ替えられた順序であることが分かる.したがって,中順に二叉探索ツリーを遍歴し,k番目のノードに戻ればよい.コードではflagを導入する小さな最適化が行われています.すなわち、k番目のノードが見つかった場合、ループを停止し、後続のループプロセスを行わないようにします.