LeetCodeテンセント50題Python実現の「二叉樹の中でK番目の小さい要素」

3331 ワード
python
タイトル
二叉探索ツリーを指定し、関数kthSmallestを記述してk番目の最小要素を検索します.
説明:kは常に有効であり、1≦k≦二叉探索ツリー要素の個数であると仮定できます.
例1:
入力:root=[3,1,4,null,2],k=1 3/1 4 2出力:1例2:
入力:root=[5,3,6,2,4,null,null,1],k=3 5/3 6/2 4/1出力:3ステップ:二叉検索ツリーが頻繁に変更され(挿入/削除操作)、k番目の小さな値を頻繁に検索する必要がある場合、kthSmallest関数を最適化する方法
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
構想
  • 二叉探索ツリーBSTには重要な性質がある:中順遍歴はソート配列として、この性質に基づいて、問題を中順遍歴k番目のノードを探す値に変換することができる.
  • によって実装される方法は、答えとカウントを格納するために2つのグローバル変数resとcountを確立することである:ノードにアクセスするたびに、カウンタ−1;count==0の場合、k番目のノードに到着したことを表し、resに答えを記録する.
  • 答えが見つかった後、遍歴を続ける必要はないので、resが空であるかどうかを判断するたびに、空でなければ直接戻ります.

    • コード#コード#
    ref:https://leetcode-cn.com/problems/two-sum/solution/kth-smallest-element-in-a-bst-ti-qian-zhong-zhi-zh/
    class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.res, self.count = None, k
        def inorder(root):
            if not root: return
            inorder(root.left)
            if self.res: return
            self.count -= 1
            if not self.count: self.res = root.val
            inorder(root.right)
        inorder(root)
        return self.res
    Pythonは、指定されたポートに基づいてサーバ/モジュールの導入を検出する方法を実現します.
    [訳]GLUTチュートリアル-レンズを移動する2