*Kth Smallest Element in a BST

题目：

Given a binary search tree, write a function kthSmallest to find the kth 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?

 

思路：

就是inorder traverse

1 public int kthSmallest(TreeNode root, int k) 2 { 3 4 ArrayList<Integer> re = new ArrayList<Integer>(); 5 // if(root==null) 6 // return re; 7 helper(root,re); 8 return re.get(k-1); 9 10 } 11 12 public void helper(TreeNode root, ArrayList<Integer> re) 13 { 14 if(root==null) 15 return; 16 helper(root.left,re); 17 re.add(root.val); 18 helper(root.right,re); 19 }

reference：http://www.programcreek.com/2014/07/leetcode-kth-smallest-element-in-a-bst-java/

 

解法二：非递归

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int kthSmallest(TreeNode root, int k) { ArrayList<Integer> res = inOrderTrav(root); return res.get(k-1); } public ArrayList<Integer> inOrderTrav(TreeNode root) { LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); ArrayList<Integer> res = new ArrayList<Integer>(); if(root==null) return res; while(root!=null||!stack.isEmpty()) { if(root!=null) { stack.push(root); root = root.left; } else { root = stack.pop(); res.add(root.val); root = root.right; } } return res; } }

 

转载于:https://www.cnblogs.com/hygeia/p/4772083.html

相关资源：JAVA上百实例源码以及开源项目