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

左手的ㄟ右手 2022-10-16 09:39 108阅读 0赞

## Topic ##

*  Binary Search
 *  Tree

## Description ##

[https://leetcode.com/problems/kth-smallest-element-in-a-bst/][https_leetcode.com_problems_kth-smallest-element-in-a-bst]

Given the `root` of a binary search tree, and an integer `k`, return the `k`th (**1-indexed**) smallest element in the tree.

**Example 1:**

![3870cb339a1d9e6cc4021778d28bac32.png][]

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

**Example 2:**

![65f586f0277f2d50f31dcafdffa6cd23.png][]

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 1⩽k⩽104
 *   0 ⩽ N o d e . v a l ⩽ 1 0 4 0 \\leqslant Node.val \\leqslant 10^4 0⩽Node.val⩽104

**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));
    	}
    }

[https_leetcode.com_problems_kth-smallest-element-in-a-bst]: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
[3870cb339a1d9e6cc4021778d28bac32.png]: /images/20221014/75b8ed42d3fc4b0590abffeff9f99120.png
[65f586f0277f2d50f31dcafdffa6cd23.png]: /images/20221014/24e11db92f0b4b50b98d8ec6e34bd510.png