二叉搜索树的第k个结点【Java版】

方法一：双函数

//新建的void函数 用于修改全局变量res；主函数负责return
public class Solution {
    private int count = 0;//全局（类）变量可以不初始化，int默认为0  //等价于private int count;
    private TreeNode res = null;//等价于private TreeNode res;
    //全局（类）变量不能这样初始化：private TreeNode result=new TreeNode();这种方法用于函数内局部变量初始化
    TreeNode KthNode(TreeNode pRoot, int k){
        count = k;
        Find(pRoot);
        return res;
    }
    void Find(TreeNode pRoot){
        if(pRoot!=null && res==null){//res==null用于剪枝加速；本题不剪枝也答案正确  //也可以用count>=0来剪枝
            Find(pRoot.left);
            if(--count == 0)res=pRoot;//找到，立即结束
            Find(pRoot.right);
        }
    }
}//时间O(N) 空间O(logN)
//指导思想：【树递归，能拆就拆】
//拆开的三大好处：接口清晰、时空高效、简化逻辑(不易写错)==>对人对机器都好

方法二：单函数（原函数上直接递归）

public class Solution {
    int count = 0;
    TreeNode KthNode(TreeNode pRoot, int k) {//单函数：代码短，但逻辑复杂
        if(pRoot != null){//dfs的剪枝尽量不要分左右子树来写，这样集中写比较好
            TreeNode left = KthNode(pRoot.left,k);
            if(left != null)return left;//帮助返回res,并拦截内层的null
            if(++count == k)return pRoot;//【一旦找到，就会剪枝、logn时间迅速向上】//找不到就一直没有return
            TreeNode right = KthNode(pRoot.right,k);
            if(right != null)return right;//帮助返回res,并拦截内层的null
        }
        return null;//最外层的null才可能返回，其他都会被拦截
    }
}//时间O(N) 空间O(logN)