給一串二元樹，在找出第 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;
}
}
}