1 題目描述


在二元搜尋樹中，找到第 k 小的節點值。

2 解法

看到二元搜尋樹就要知道，中序遍歷的結果就是一個排序好的陣列。因此我們可以透過中序遍歷的方式，來找到第 k 小的節點值。也就是先 left - root - right 的方式遍歷，當我們遍歷到第 k 個節點時，就可以回傳。大概可以這樣思考：

  1. 我們先走到底，也就是一直往左走，直到走到最左邊的節點。
  2. 當觸底的時候，我們開始計數，每次遍歷到一個節點，就把 count+1。
  3. 當 count 與 k 相等時，就回傳當前節點的值。
  4. 否則，遍歷右邊的節點。
    那我們開始來一步步拆解這個問題吧！

Step 1 我們先走到底

1
2
3
4
5
6
def inorder(root):
    # 如果沒有節點了，就停止
    if not root:
        return
    # 先走到底
    inorder(root.left)

Step 2 當觸底的時候，我們開始計數

1
2
3
4
5
6
7
def inorder(root):
    if not root:
        return
    inorder(root.left)
    # 這時候的root就是最左邊的節點
    # 開始計數
    count += 1

Step 3 當 count 與 k 相等時，找到第k的最小值。

1
2
3
4
5
6
7
8
9
def inorder(root):
    if not root:
        return
    inorder(root.left)
    count += 1
    # 如果count等於k，就回傳當前節點的值
    if count == k:
        ans = root.val
        return

到這裡幾乎就完成一大半了，但是上面的程式碼只有遍歷到最左邊的節點，我們還需要遍歷右邊的節點。因此我們可以透過遞歸的方式，來遍歷右邊的節點。
Step 4 遍歷右邊節點

1
2
3
4
5
6
7
8
9
10
def inorder(root):
    if not root:
        return
    inorder(root.left)
    count += 1
    if count == k:
        ans = root.val
        return 
    # 遍歷右邊的節點
    inorder(root.right)

這樣就完成了！！完整的程式碼如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    ans = None
    num = 0
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        def inorder(root: Optional[TreeNode], k: int):

            if root is None:
                return
            inorder(root.left, k)
            self.num = self.num + 1
            if self.num == k:
                self.ans = root.val
                return
            inorder(root.right, k)

        inorderTraversal(root, k)
        return self.ans

2.2 使用迭代的方式

這裡我們可以使用迭代的方式來解這個問題，也就是使用stack來模擬遞歸的方式。而概念也是一樣

  1. 先走到底最左邊
  2. 開始計數
  3. 當 count 與 k 相等時，就回傳當前節點的值
  4. 否則，遍歷右邊的節點
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        cur = root
        count = 0
        while cur or stack:
            # 1 先走到底最左邊
            while cur:
                stack.append(cur)
                cur = cur.left
            # 2 從最左邊開始計數
            node = stack.pop()
            count += 1
            # 3 如果count等於k，就回傳當前節點的值
            if count == k:
                return node.val
            # 遍歷右邊的節點，也會被塞入stack中
            cur = node.right

3 結語

這題不難，但是我也是笨笨的思路沒有想清楚，腦子第一個反應應該是要出現我要先走到最底層，然後開始計數的程式邏輯不夠清晰。

1
2
3
4
def mostLeft(root):
    if not root:
        return
    mostLeft(root.left)
1
2
3
4
def mostLeft(root):
    while root.left:
        root = root.left
    return root