Leetcode題解 Python & C#：五月挑戰DAY20 Smallest Element in a BST

給一串二元樹，在找出第 k 個小的元素。

這題目給的二元樹是比較嚴謹的，子樹左邊皆小於自身，右邊皆大於自身。

因此，左邊最底層的是最小的，接著其父，其父之右子樹，這與「in-order」的 traversal 方式是一樣的。

所以用上這樣的方法，並且加入「第幾小的序數」就能得到題目所求。

對於二元樹的題目，各種traversal模式都要熟練，才會很快地想到寫法。

Python(遞迴函數)

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        self.result = 0
        def dfs(node, rank):
            if not node: return rank
            rank = dfs(node.left, rank) + 1
            if rank == k: self.result = node.val               
            rank = dfs(node.right, rank)
            return rank
        
        dfs(root, 0)
        return self.result

Python(官方)

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        stack = []        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0: return root.val                
            root = root.right

C#

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var stack = new Stack();
        while(true)
        {
            while(!(root is null))
            {
                stack.Push(root);
                root = root.left;
            }
            root = stack.Pop();
            k--;
            if(k==0){return root.val;}
            root = root.right;                
        }
    }
}