剑指OfferJZ62:二叉搜索树的第k小个结点-java版

JZ62:给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点

中序遍历二叉树的每个节点，最终得到的序列是单调递增序列，那么第k次遍历到的节点就是第k小节点 中序遍历：对于每一个节点，先遍历当前节点的左孩子，接着遍历当前节点，最后遍历当前节点的右孩子 二叉树的三种遍历方法：

中序遍历为：1,2,3,4,5,6 那么第k小节点（第三次遍历到的数）为3

public class Solution {
   private TreeNode ans;//返回的最终的结果
    private int index;//标记中序遍历时当前节点是第几次遍历到的

    TreeNode KthNode(TreeNode pRoot, int k) {
        //初始化变量
        index=1;
        ans=null;
        //中序遍历
        if(k!=0 && pRoot!=null) {
            solve(pRoot, k);
        }
        return ans;
    }

    private void solve(TreeNode node,int k){
        if(ans==null) {
            //先遍历当前节点的左孩子
            if (node.left != null) {
                solve(node.left, k);
            }
            if (index == k) {
                ans = node;
            }
            index++;
            //再遍历当前节点的右孩子
            if (node.right != null) {
                solve(node.right, k);
            }
        }
    }
}

拓展：求二叉搜索树的第k大节点 方法类似于上面 这里是先遍历当前节点的右孩子，接着遍历当前节点的，最后遍历当前节点的左孩子（非二叉树遍历方法）

 class Solution {
    
     private TreeNode ans;//返回的最终的结果
    private int index;//标记中序遍历时当前节点是第几次遍历到的

    public int KthNode(TreeNode root, int k) {
        //初始化变量
        index=1;
        ans=null;
        //中序遍历
        if(k!=0 && root!=null) {
            solve(root, k);
        }
        return ans.val;
    }

    private void solve(TreeNode node,int k){
        if(ans==null) {
            //先遍历当前节点的右孩子
            if (node.right != null) {
                solve(node.right, k);
            }
            //这里相当于遍历了当前节点
            if (index == k) {
                ans = node;
            }
            index++;
            //再遍历当前节点的左孩子
            if (node.left != null) {
                solve(node.left, k);
            }
        }
    }
}