230. Kth Smallest Element in a BST

Question: Kth Smallest Element in a BST
Solution

1. 找第 k 小，因為是找小，所以要先一直往左邊找: node.left → node.left → node.left → DFS
2. 這些一路往下找的 node.left 必須記錄起來，讓小的在最上面，最好拿取 → stack
3. 如果一直往左找，找到底了，Node == Null 了，就把 stack 最上面 pop 出來，就會是第一個最小值。此時需要一個變數 n = 0，每 pop 出一個值 n += 1，直到 + 到跟 k 一樣大。
4. pop 出來後要繼續看這個 node 有沒有 right child，有個話就重複看 right child 的 left children，一路看，一路加到 stack 裡(回到步驟1)

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

stack = []

n = 0

curr = root

while curr or stack:

while curr:

stack.append(curr)

curr = curr.left

curr = stack.pop()

n += 1

if n == k:

return curr.val

curr = curr.right

Video Solution