JZ54二叉搜索树的第k个节点

题目

给定一棵结点数为n 二叉搜索树             ，请找出其中的第 k 小的TreeNode结点值 
  
  
  
  
  
  
。

返回第k小的节点值即可 不能查找的情况 
  
 
  
 
  
 
  
 
  
 
  
 
 ，如二叉树为空













，则返回-1 
  
  
  
  
  
  ，或者k大于n等等 
  
  
  
  
  
  
 ，也返回-1 保证n个节点的值不一样

思路

算法实现

根据二叉搜索树的性质

 


 


 


 


 


 


，左子树的元素都小于根节点 
 
 
 
 
 
 ，右子树的元素都大于根节点
  
  
  
  
  
  
 。因此它的中序遍历（左中右）序列正好是由小到大的次序 
   
   
   
   
   
   
 ，

因此我们可以尝试递归中序遍历
 

 

 

 

 

 

，也就是从最小的一个节点开始
 

 

 

 

 

 

 ，找到k个就是我们要找的目标
 


 


 


 


 


 


 。

具体做法：

step 1：设置全局变量count记录遍历了多少个节点             ，res记录第k个节点 
 
 
 
 
 
 
。

step 2：另写一函数进行递归中序遍历 

 
 

 
 

 
 

 
 

 
 

 
 

，当节点为空或者超过k时












，结束递归                    ，返回
   
   
   
   
   
   
 。

step 3：优先访问左子树 
 
 
 
 
 
 
 
 
 
 
 
 
，再访问根节点



















，访问时统计数字             ，等于k则找到
 

 

 

 

 

 

 。

step 4：最后访问右子树 

 

 

 

 

 

 
。

代码

package mid.JZ54二叉搜索树的第k个节点; import java.util.*; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class Solution { /** * 代码中的类名 
  
  
  
  
  
  
、方法名
  
  
  
  
  
  
 、参数名已经指定 
  
 
  
 
  
 
  
 
  
 
  
 
 ，请勿修改













，直接返回方法规定的值即可 * * @param proot TreeNode类 * @param k int整型 * @return int整型 */ public int KthNode(TreeNode proot, int k) { midOrder(proot, k); if (res != null) { return res.val; } else { return -1; } } public int KthNode2(TreeNode proot, int k) { // write code here if(proot == null || k == 0) return -1; List<Integer> res = new ArrayList<>(); def(proot, res); System.out.println(res.size()); System.out.println(k); System.out.println(res.size()< k); if(res.size()< k) return -1; Collections.sort(res); return res.get(k-1); } public void def(TreeNode proot, List<Integer> res) { if (proot == null) return; def(proot.left, res); res.add(proot.val); def(proot.right, res); } //记录返回的节点 private TreeNode res = null; //记录中序遍历了多少个 private int count = 0; public void midOrder(TreeNode root, int k) { if (root == null || count > k) return; midOrder(root.left, k); count++; if (count == k) { res = root; } midOrder(root.right, k); } }