230. Kth Smallest Element in a BST

BST, and kth , order problem => think about inorder traversal

but be careful, the global variable count is necessary! (if use recursion)

or the result will change in the recursion process again

in this ex, k will pass into inorder(), twice, and all are k = 1, so k-- , k == 0, there will be two times get the result, and the second will replace the first result!

even if you dont use global result, the behavior is the same, k = 1 pass to inorder twice

traversal 都是遍例所有節點, 所以是 O(n), 因為 recursive 所以空間也需要 O(n)

use count!

time: O(n)

space: O(n)

class Solution {
    
    int count = 0;
    int res = 0;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        helper(root, k);
        return res;
    }
    
    private void helper(TreeNode root, int k) {
        if (root == null) return;
        helper(root.left, k);
        count--;
        if (count == 0) {
            res = root.val;
        }
        helper(root.right, k);

    }
}

stack - iteration

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        
        // k-1 times traversal
        for (int i = 0; i < k-1; i++) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                node = node.right;
                
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
            }
        }
        return stack.peek().val;
    }
}

latest

early stop, if find k, we won't keep going, so

T: O(k)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int[] curK = new int[1];
        curK[0] = k;
        int[] result = new int[1];
        dfs(root, curK, result);
        return result[0];
    }
    private void dfs(TreeNode node, int[] curK, int[] result) {
        if (node == null) {
            return;
        }
        if (curK[0] > 0) {
            dfs(node.left, curK, result);
        }

        curK[0]--;
        if (curK[0] == 0) {
            result[0] = node.val;
            return;
        }
        
        if (curK[0] > 0) {
            dfs(node.right, curK, result);
        }
    }
}