LeetCode: Kth Smallest Element in a BSTを解く

問題

May Leetcoding Challange Complementの21日目です。 5月も下旬。早い。

leetcode.com

BSTのトラバースする問題です。

解き方

解き方は極めてシンプルで、BSTをDFS - Inorderでなめていき、Arrayに詰めてアクセスすればOK。

木のInorder、Preorder、Postorderについてはこの記事がわかりやすい。

www.geeksforgeeks.org

回答

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        res = []
        def dfs(root: TreeNode):
            if not root:
                return
            
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res[k-1]

公式回答がエレガントでした。

class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        def inorder(r):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
    
        return inorder(root)[k - 1]

計算量

時間計算量: O(N)
空間計算量: O(N)