您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

LeetCode - Medium - 230. Kth Smallest Element in a BST

Topic

  • Binary Search
  • Tree

Description

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element 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

Constraints:

The number of nodes in the tree is n.

  • 1 ⩽ k ⩽ 1 0 4 1 \leqslant k \leqslant 10^4 1k104
  • 0 ⩽ N o d e . v a l ⩽ 1 0 4 0 \leqslant Node.val \leqslant 10^4 0Node.val104

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Analysis

方法一:我写的递归法(BST的中序遍历)

方法二:我写的迭代法

方法三:别人写的迭代法

Submission

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class KthSmallestElementInABST {
	
	//方法一:我写的递归法(BST的中序遍历)
    public int kthSmallest(TreeNode root, int k) {
    	int[] result = {-1}, count = {0};
    	inorder(root, k, result, count);
        return result[0];
    }
    
    private void inorder(TreeNode root, int k, int[] result, int[] count) {
    	if(root == null || result[0] != -1) return;
    	
    	inorder(root.left, k, result, count);
    	if(++count[0] == k) {
    		result[0] = root.val;
    		return;
    	}
    	inorder(root.right, k, result, count);
    }
    
    //方法二:我写的迭代法
    public int kthSmallest2(TreeNode root, int k) {
    	LinkedList<Object[]> stack = new LinkedList<>();
    	stack.push(new Object[] {root, 0});//0, 1, 2, 3 = 左,中,右,pop
    	
    	int count = 0;
    	while(!stack.isEmpty()) {
    		Object[] arr = stack.peek();
    		TreeNode node = (TreeNode)arr[0];
    		int state = (int)arr[1];
    		
    		if(state == 0) {
    			if(node.left != null)
    				stack.push(new Object[] {node.left, 0});
    			arr[1] = 1;
    		}else if(state == 1) {
    			if(++count == k)
    				return node.val;
    			arr[1] = 2;
    		}else if(state == 2) {
    			if(node.right != null) 
    				stack.push(new Object[] {node.right, 0});
    			arr[1] = 3;
    		}else {
    			stack.pop();
    		}
    	}
    	return -1;
    }
    
    //方法三:别人写的迭代法
    public int kthSmallest3(TreeNode root, int k) {
    	LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode p = root;
        int count = 0;
        
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);  // Just like recursion
                p = p.left;   
                
            } else {
               TreeNode node = stack.pop();
               if(++count == k) return node.val; 
               p = node.right;
            }
        }
        
        return -1;
    }
    
}

Test

import static org.junit.Assert.*;
import org.junit.Test;

import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;

public class KthSmallestElementInABSTTest {

	@Test
	public void test() {
		KthSmallestElementInABST obj = new KthSmallestElementInABST();

		TreeNode root1 = BinaryTree.integers2BinaryTree(3, 1, 4, null, 2);
		TreeNode root2 = BinaryTree.integers2BinaryTree(5, 3, 6, 2, 4, null, null, 1);
		
		assertEquals(1, obj.kthSmallest(root1, 1));
		assertEquals(3, obj.kthSmallest(root2, 3));
		
		assertEquals(1, obj.kthSmallest2(root1, 1));
		assertEquals(3, obj.kthSmallest2(root2, 3));
		
		assertEquals(1, obj.kthSmallest3(root1, 1));
		assertEquals(3, obj.kthSmallest3(root2, 3));
	}
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进