题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
题目来源：剑指Offer

• 思路
  从二叉搜索树中找第k小节点等价于将此树按中序排序后找第k个节点。

非递归实现

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || k <= 0)
            return null;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int num = 0;
        TreeNode root = pRoot; //为了不破坏原来的节点，也可以不加
        
        while(root != null || stack.isEmpty() == false){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            
            TreeNode node = stack.pop();
            num ++;
            if(num == k)
                return node;
            
            root = node.right;
        }
        
        return null;
    }
}

递归实现

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    
    int cnt = 0;
    
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || k <= 0)
            return null;
        
        TreeNode node = KthNode(pRoot.left, k);
        if(node != null)
            return node;

        cnt ++;
        if(cnt == k)
            return pRoot;

        node = KthNode(pRoot.right, k);
        if(node != null)
            return node;
        
        return null;
    }
}

其中 if(node != null)return node; 的作用是把在下层递归中找到的结果返回最顶层（如果node为空则表示还没有找到符合要求的节点，需要往下判断接着找，反之则为找到了）；如果不加的话最终找到的结果只会返回到当前递归的上一个递归中，最后无法传递到最顶层