230. Kth Smallest Element in a BST

题目描述

Given a binary search tree, write a functionkthSmallestto find thekth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

解题方法

    //container with DFS
    //Runtime complexity is O(n): worst case
    /*public int kthSmallest(TreeNode root, int k){
        if(root == null){
            return -1;
        }
        List<Integer> list = new ArrayList<>();
        int[] count = new int[]{k};
        DFS(root, count, list);
        return (list.size() > 0) ? list.get(0) : -1;
    }
    private void DFS(TreeNode root, int[] count, List<Integer> list){
        if(root == null){   //put nothing
            return;
        }
        DFS(root.left, count, list);
        if(count[0] == 1){
            list.add(root.val);
            return;
        }
        count[0] = count[0] - 1;
        DFS(root.right, count, list);

    //iterative
    public int kthSmallest(TreeNode root, int k){
        Stack<TreeNode> stack = new Stack<>();
        if(root == null){return -1;}
        while(root != null){
            stack.push(root);
            root = root.left;
        }

        while(k > 0){
            TreeNode node = stack.pop();
            if(k == 1){
                return node.val;
            }
            k--;
            root = node.right;
            while(root != null){
                stack.push(root);
                root = root.left;
            }
        }
        return -1;
    }