首页 > itarticle > kth element in bst

kth element in bst

admin 11月 11, 2020 0

Problem:

Given a BST and a number k, find the kth smallest element in the BST

分析

同样的还是变相考察树的前序遍历。每次从栈中pop一个元素，k就减1.直至k为0.

AC1:


 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class  {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode n = root;
        while(n != null) {
            stack.push(n);
            n = n.left;
        }
        
        while(k > 0 && (n != null || !stack.isEmpty())) {
            if(n == null) {
                n = stack.pop();
                if(--k == 0) return n.val;
                n = n.right;
            } else {
                stack.push(n);
                n = n.left;
            }
        }
        return n.val;
    }
}

AC2:


 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class  {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode n = root;
        while(n != null) {
            stack.push(n);
            n = n.left;
        }
        while (k > 0 && !stack.isEmpty()) {
            n = stack.pop();
            if (--k == 0) return n.val;
            TreeNode right = n.right;
            while (right != null) {
                stack.push(right);
                right = right.left;
            }
        }
        return n.val;
    }
}

AC1没有那么直观，建议使用AC2，毕竟是我们熟悉的形式。