2015年11月3日星期二

Leetcode 230 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.
Solution 1: use in-order traversal and counter the kth number.
 public class Solution {  
   public int kthSmallest(TreeNode root, int k) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         if (--k==0) return x.val;  
         x=x.right;  
       }  
     }  
     return 0;  
   }  
 }  

没有评论:

发表评论