PattySung

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

<解題>

用count 用於計數遍歷到的節點數量，變數 result 用於儲存第 k 小的節點的值
在每次遞迴中，先遞迴處理左子樹，然後對當前節點進行計數 count++。如果 count 等於 k，表示已經遍歷到第 k 個節點，將當前節點的值給 result。最後，遞迴處理右子樹。
當遍歷結束後，變數 result 將保存第 k 小的元素的值，並在 kthSmallest 方法中返回。

Recursive:

class Solution {
    int count = 0;
    int result = Integer.MIN_VALUE;

public int kthSmallest(TreeNode root, int k) {
    traverse(root, k);
    return result;
}

public void traverse(TreeNode root, int k) {
    if(root == null) return;
    traverse(root.left, k);
    count ++;
    if(count == k) result = root.val;
    traverse(root.right, k);       
}
}

Time: O(n) Space: O(n)

Iterative:

class Solution {
   
 public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<TreeNode>();
     int count = 0;
     
     while(!stack.isEmpty() || root != null) {
         if(root != null) {
             stack.push(root);  // Just like recursion
             root = root.left;   
             
         } else {
            TreeNode node = stack.pop();
            if(++count == k) return node.val; 
            root = node.right;
         }
     }
     
     return Integer.MIN_VALUE;
 }
}

class Solution {
   
 public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    
    while (true){
        while (root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (--k == 0) return root.val;
        root = root.right;
    }
 }
}

Leetcode-230. Kth Smallest Element in a BST

<解題>