62-⼆叉搜索树的第k个结点

题⽬描述

给定⼀棵⼆叉搜索树，请找出其中的第 k ⼩的 TreeNode 结点。

示例1
输⼊：{5,3,7,2,4,6,8},3
返回值：{4}

思路及解答

本题的思路主要是使⽤递归，由于⼆叉搜索树的每⼀个节点都⽐⾃⼰的左节点⼤，⽐⾃⼰的右节点⼩，

那么如果求解第 k ⼩元素，我们不妨使⽤ k 不断减⼩，直到1的时候就是最⼩的元素。

• 如果 root 为空，那么直接返回，否则，⽤ k 减掉左⼦树的节点数：
• 如果结果为 1 ，说明当前的 root 节点就是第 k 个节点（左⼦树有 k-1 个节点）；
• 如果结果⼩于 1 ，那么说明左⼦树的节点⼤于 k-1 个，第 k 个元素在左⼦树中，使⽤左⼦树进⾏递归；
• 如果结果⼤于 1 ，说明左⼦树的节点不够 k-1 个，那么第 k 个节点肯定是在右⼦树中。
  • 那么获取⼦树节点个数的时候，输⼊的是 k ，如果节点数⼤于 k ，结果就是负数，如果节点数⼩于k ，结果就是正数。如果根节点为空，则直接返回 k ；否则先处理左⼦树，然后 k-- （表示减掉⾃身），然后处理右⼦树。

public class Solution62 {
     public static void main(String[] args) {
         TreeNode root = new TreeNode(5);
         root.left = new TreeNode(4);
         root.left.left = new TreeNode(3);
         root.left.left.left = new TreeNode(2);
         root.left.left.left.left = new TreeNode(1);
         TreeNode result = new Solution62().KthNode(root,3);
         System.out.println(result);
     }
    
     TreeNode KthNode(TreeNode pRoot, int k) {
         if(pRoot==null){
         	return pRoot;
         }else{
             int left = getNum(pRoot.left,k);
             if(left==1){
         		return pRoot;
         	}else if(left<1){
         		return KthNode(pRoot.left,k);
             }else{
                return KthNode(pRoot.right,left-1);
             }
     	}
     }
    
     int getNum(TreeNode root,int k){
         if(root==null){
         	return k;
         }
         int left = getNum(root.left,k);
         left--;
         return getNum(root.right,left);
     }
}

利用二叉搜索树特性

其实根本不需要这么麻烦，因为⼆叉搜索树，如果使⽤中序遍历就可以直接得到第k个节点，也就是第k⼩的数值。

public class Solution {
     int count = 0; 
     int result = -1;
    
     public int KthNode (TreeNode proot, int k) {
         if(proot == null || k <= 0) return -1;
         KthNode(proot.left,k);
         ++count;
         if(count == k) return result = proot.val;
         KthNode(proot.right,k);
         return result;
     }
}

当然，也可以写出⾮递归的版本，借助堆栈即可：

public class Solution54 {
     public int KthNode(TreeNode proot, int k) {
         if (proot == null) return -1;
         Stack<TreeNode> stack = new Stack<>();
         stack.push(proot);
         TreeNode node = proot;
         int i = 0;
         while (!stack.isEmpty()) {
             //左⼦树
             while (node.left != null) {
                 stack.push(node.left);
                 node = node.left;
             }
             i++;
             if (i == k) {
            	 return stack.pop().val;
             }
             TreeNode temp = stack.pop();
             // 右⼦树
             if (temp.right != null) {
                 stack.push(temp.right);
                 node = temp.right;
             }
         }
         return -1;
     }
}