本文共 1081 字，大约阅读时间需要 3 分钟。

题目：给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

思路1：递归方式

class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(){
   					}		TreeNode(int val){
   			this.val = val;		}		TreeNode(int val,TreeNode left,TreeNode right){
   			this.val = val;			this.left = left;			this.right = right;		}	}	  // 递归	 public int kthSmallest(TreeNode root, int k) {
   		 ArrayList
   
     res = new ArrayList<>();		 res = inorder(root,res);		 return res.get(k-1);	 }	 	 // 存储	 private ArrayList
    
      inorder(TreeNode root,ArrayList
     
       res){
   		 if(root==null) {
   			 return res;		 }		 		 // 左子树		 inorder(root.left,res);		 // 当前节点的值处理		 res.add(root.val);		 // 右子树		 inorder(root.right,res);		 		 return res;	 }
     
    
   

思路2：迭代方式

// 迭代	 public int kthSmallest_2(TreeNode root, int k) {
   		 Stack
   
     stack = new Stack<>();		 		 while(true) {
   			 while(root!=null) {
   				 stack.push(root);				 root = root.left;			 }			 root = stack.pop();			 if(--k==0) {
   				 return root.val;			 }			 root = root.right;		 }	 }
   

转载地址：http://awwdf.baihongyu.com/