JZ62 二叉搜索树的第k个结点

原题链接

描述

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

示例1

输入：{5,3,7,2,4,6,8},3
返回值：4
说明：按结点数值大小顺序第三小结点的值为4   

思路

中序遍历二叉搜索树第 k 次访问到的结点就是第 k 小的结点。所以主要是一个中序遍历。

解答

public class Solution {
    static TreeNode res = null;
    static int i = 0;

    static void inOrder(TreeNode root, int k) {
        if (root.left != null) inOrder(root.left, k);
        if (i++ == k -1) res = root;
        
        if (root.right != null) inOrder(root.right, k);
    }

    // 中序遍历 k 次
    static TreeNode KthNode(TreeNode pRoot, int k) {
                if (pRoot ==null) return null;

        inOrder(pRoot, k);
        return res;
    }
}

JZ62 二叉搜索树的第k个结点

原文：https://www.cnblogs.com/klaus08/p/15106684.html